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:
CreatorsEmailORCIDORCID Put Code
Schaudt, OliverUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
Weil, VeraUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
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:
KeywordsLanguage
LINE GRAPHS; OMEGA; DELTA; CHI; THEOREMMultiple languages
MathematicsMultiple languages
URI: http://kups.ub.uni-koeln.de/id/eprint/39463

Downloads

Downloads per month over past year

Altmetric

Export

Actions (login required)

View Item View Item