On bounding the difference between the maximum degree and the chromatic number by a constant

Abstract

We provide a finite forbidden induced subgraph characterization for the graph class ${{\rm Y}}_k$, for all $k\in {\mathbb{N}}_0$, which is defined as follows. A graph is in ${{\rm Y}}_k$ if for any induced subgraph, $\Delta \le \chi -1+k$ holds, where $\Delta$ is the maximum degree and $\chi$ is the chromatic number of the subgraph. We compare these results with those given in [O. Schaudt, V. Weil, On bounding the difference between the maximum degree and the clique number, Graphs and Combinatorics 31(5), 1689-1702 (2015). DOI: 10.1007/s00373-014-1468-3], where we studied the graph class ${\Omega }_k$, for $k\in {\mathbb{N}}_0$, whose graphs are such that for any induced subgraph, $\Delta \le \omega -1+k$ holds, where $\omega$ denotes the clique number of a graph. In particular, we give a characterization in terms of ${\Omega }_k$ and ${{\rm Y}}_k$ of those graphs where the neighborhood of every vertex is perfect.

10 pages, 4 figures

References in corpus (1)

• House of Graphs: a database of interesting graphs