Universität zu Köln

Schaudt, Oliver and Weil, Vera (2015). On Bounding the Difference of the Maximum Degree and the Clique Number. Graphs Comb., 31 (5). S. 1689 - 1703. TOKYO: SPRINGER JAPAN KK. ISSN 1435-5914

Full text not available from this repository.

Abstract

For every , we consider graphs in which for any induced subgraph, holds, where is the maximum degree and is the maximum clique number of the subgraph. We give a finite forbidden induced subgraph characterization for every . As an application, we find some results on the chromatic number of a graph. B. Reed stated the conjecture that for every graph, holds. Since this inequality is fulfilled by graphs in which holds, our results provide a hereditary graph class for which the conjecture holds.

Item Type:	Journal Article
Creators:	Creators Email ORCID ORCID Put Code Schaudt, Oliver UNSPECIFIED UNSPECIFIED UNSPECIFIED Weil, Vera UNSPECIFIED UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-394638
DOI:	10.1007/s00373-014-1468-3
Journal or Publication Title:	Graphs Comb.
Volume:	31
Number:	5
Page Range:	S. 1689 - 1703
Date:	2015
Publisher:	SPRINGER JAPAN KK
Place of Publication:	TOKYO
ISSN:	1435-5914
Language:	English
Faculty:	Unspecified
Divisions:	Unspecified
Subjects:	no entry
Uncontrolled Keywords:	Keywords Language LINE GRAPHS; OMEGA; DELTA; CHI; THEOREM Multiple languages Mathematics Multiple languages
URI:	http://kups.ub.uni-koeln.de/id/eprint/39463