On the chromatic number of a graph with two forbidden subgraphs (Q1122586): Difference between revisions

A well-known result of Vizing asserts that the edge chromatic number of a graph G equals either \(\Delta\) (G) or \(\Delta (G)+1\) when \(\Delta\) (G) is the maximum degree of G. By using Beineke's forbidden-induced-subgraph characterization of line graphs, \textit{S. A. Choudum} [Q. J. Math., Oxf. II. Ser. 28, 257-270 (1977; Zbl 0364.05023)] restated this result as follows: If G is a simple graph whose maximum clique has d(G) vertices, then \(\chi\) (G), the (vertex) chromatic number of G, is at most \(d(G)+1\) provided that G has no induced subgraph isomorphic to any of nine particular graphs. Choudum, Javdekar, and Kierstead sharpened this result by proving that the conclusion remains true when certain of the nine graphs are eliminated from the hypothesis. The best such result was proved by \textit{H. A. Kierstead} [J. Comb. Theory, Ser. B 36, 156-160 (1984; Zbl 0541.05027)] who showed that \(\chi (G)\leq | d(G)+1\) provided that G has no induced subgraph isomorphic to \(K_{1,3}\) or \(K_ 5-e\). In this paper, the author proves that the same bound on \(\chi\) (G) holds provided that G has no induced subgraph isomorphic to either \(K_{1,3}\) or the graph obtained from \(K_ 5\) by deleting two adjacent edges.