Weil, Vera and Schaudt, Oliver (2017). On bounding the difference between the maximum degree and the chromatic number by a constant. Discret Appl. Math., 231. S. 228 - 235. AMSTERDAM: ELSEVIER SCIENCE BV. ISSN 1872-6771

Full text not available from this repository.

Abstract

We provide a finite forbidden induced subgraph characterization for the graph class gamma(k), for all k is an element of N-o, which is defined as follows. A graph is in gamma(k) if for any induced subgraph, Delta <= chi -1+ k holds, where Delta is the maximum degree and chi is the chromatic number of the subgraph. We compare these results with those given in Schaudt and Weil (2015), where we studied the graph class Omega(k), for k is an element of N-o, whose graphs are such that for any induced subgraph, Delta <= omega-1+k holds, where w denotes the clique number of a graph. In particular, we give a characterization in terms of Omega(k) and gamma(k) of those graphs where the neighborhood of every vertex is perfect. (C) 2016 Elsevier B.V. All rights reserved.

Item Type: Journal Article
Creators:
CreatorsEmailORCIDORCID Put Code
Weil, VeraUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
Schaudt, OliverUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
URN: urn:nbn:de:hbz:38-211105
DOI: 10.1016/j.dam.2016.11.018
Journal or Publication Title: Discret Appl. Math.
Volume: 231
Page Range: S. 228 - 235
Date: 2017
Publisher: ELSEVIER SCIENCE BV
Place of Publication: AMSTERDAM
ISSN: 1872-6771
Language: English
Faculty: Unspecified
Divisions: Unspecified
Subjects: no entry
Uncontrolled Keywords:
KeywordsLanguage
GRAPHSMultiple languages
Mathematics, AppliedMultiple languages
Refereed: Yes
URI: http://kups.ub.uni-koeln.de/id/eprint/21110

Downloads

Downloads per month over past year

Altmetric

Export

Actions (login required)

View Item View Item