# 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.

Download: |
PDF
- Accepted Version
Download (172kB) |
---|---|

Editorial actions: |
View Item (Login required) |

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 |