Universität zu Köln

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:	Creators Email ORCID ORCID Put Code Weil, Vera UNSPECIFIED UNSPECIFIED UNSPECIFIED Schaudt, Oliver UNSPECIFIED UNSPECIFIED UNSPECIFIED
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:	Faculty of Mathematics and Natural Sciences
Divisions:	Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science
Subjects:	no entry
Uncontrolled Keywords:	Keywords Language GRAPHS Multiple languages Mathematics, Applied Multiple languages
Refereed:	Yes
URI:	http://kups.ub.uni-koeln.de/id/eprint/21110