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

We provide a finite forbidden induced subgraph characterization for the graph class gamma(k), for all k is an element of N-o, which is defined as follows. A graph is in gamma(k) if for any induced subgraph, Delta <= 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 Schaudt and Weil (2015), where we studied the graph class Omega(k), for k is an element of N-o, whose graphs are such that for any induced subgraph, Delta <= omega-1+k holds, where w denotes the clique number of a graph. In particular, we give a characterization in terms of Omega(k) and gamma(k) of those graphs where the neighborhood of every vertex is perfect. (C) 2016 Elsevier B.V. All rights reserved