On Bounding the Difference of the Maximum Degree and the Clique Number

We provide a finite forbidden induced subgraph characterization for the graphclass $\varUpsilon_k$, for all $k \in \mathbb{N}_0$, which is defined asfollows. A graph is in $\varUpsilon_k$ if for any induced subgraph, $\Delta\leq \chi -1 + k$ holds, where $\Delta$ is the maximum degree and $\chi$ is thechromatic number of the subgraph. We compare these results with those given in [O. Schaudt, V. Weil, Onbounding 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 $\varOmega_k$, for$k \in \mathbb{N}_0$, whose graphs are such that for any induced subgraph,$\Delta \leq \omega -1 + k$ holds, where $\omega$ denotes the clique number ofa graph. In particular, we give a characterization in terms of $\varOmega_k$and $\varUpsilon_k$ of those graphs where the neighborhood of every vertex isperfect.Comment: 10 pages, 4 figure