3-Colorability and forbidden subgraphs. I: Characterizing pairs Original Research Article

In this paper we investigate chromatic aspects for graphs with forbidden induced subgraphs with emphasis on the question of 3-colorability. In the main part all possible pairs (A,B) of forbidden induced subgraphs, s.t. every A- and B-free graph is 3-colorable, are determined. Moreover, this is embedded in a more general problem and the main result extends Vizingʹs classical edge coloring result.