Nordhaus and Gaddum proved in 1956 that the sum of the chromatic number χ of a graph G and its complement is at most | G | + 1 . The Nordhaus–Gaddum graphs are the class of graphs satisfying this inequality with equality, and are well-understood. In this paper we consider a hereditary generalization: graphs G for which all induced subgraphs H of G satisfy χ ( H ) + χ ( H ¯ ) ≥ | H | . We characterize the forbidden induced subgraphs of this class and find its intersection with a number of common classes, including line graphs. We also discuss χ -boundedness and algorithmic results.

The complexity of testing whether a graph contains an induced odd cycle of length at least five is currently unknown. In this paper we show that this test can be done in polynomial time if the input graph has no induced subgraph isomorphic to the bull (a triangle with two disjoint pendant edges).