On bounding the difference of the maximum degree and clique number

Weil, Vera and Schaudt, Oliver (2015) On bounding the difference of the maximum degree and clique number.
Published in: Graphs and Combinatorics Vol. 31 (5). pp. 1689-1702. ISSN 0911-0119

Abstract

For every k ∈ ℕ0, we consider graphs in which for any induced subgraph, Δ ≤ ω−1+k 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 k. As an application, we find some results on the chromatic number χ of a graph. B.Reed stated the conjecture that for every graph, χ ≤ ⌈Δ+ω+1 / 2⌉ holds. Since this inequality is fulfilled by graphs in which Δ ≤ ω+2 holds, our results provide a hereditary graph class for which the conjecture holds.


Actions:
Download: [img] PDF - Accepted Version
Download (168Kb)
Export as:
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: UNSPECIFIED
Depositing User: Dr. Vera Weil
Date Deposited: 03 Nov 2015 12:57
Last Modified: 03 Nov 2015 13:14
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/891