CHROMATIC BOUNDS FOR A CLASS OF GRAPHS
S.A. Choudum · The Quarterly Journal of Mathematics · 1977
VIZING's theorem, that the edge chromatic number of a graph G is either max deg(G) or max deg(G)+1 can be restated as: if a graph G has no induced subgraph isomorphic to any of the nine forbidden subgraphs of line graphs, then the (vertex) chromatic number of G is either d or d + 1 where d is the maximum number of vertices in a clique in G. In this paper it is proved that if a graph G has no induced subgraph isomorphic to any of the graphs K1,3K5−e, G3 and G4 (these graphs are four of the nine forbidden subgraphs of line graphs), then the chromatic number of G is either d or d + 1. (Refer to Figure 1 for the forbidden subgraphs G1−G9.) A similar theorem forbidding the four subgraphs K1,3, K5−e, G5 and G6 is also proved.