On bounding the difference of the maximum degree and clique number
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.
- Accepted Version
|Editorial actions:||View Item (Login required)|
|Depositing User:||Dr. Vera Weil|
|Date Deposited:||03 Nov 2015 12:57|
|Last Modified:||03 Nov 2015 13:14|