Some applications of Vizing's theorem to vertex colorings of graphs

✍ Scribed by Henry A. Kierstead; James H. Schmerl

• Publisher: Elsevier Science
• Year: 1983
• Tongue: English
• Weight: 812 KB
• Volume: 45
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(83)90043-2

✦ Synopsis

In this paper we shall study the relationships between the following three families of assertions: C(n): If G is a graph that does not induce & or KS-e and w(G) 6 n. then x(G)rn+l. C'(n): If M is a multigraph such that A(M)< n, p(M)<2

and M does not contain a S-sided triangle (i.e., a triangle with a multiple edge), then x'(M)Gn+l.

J(m): If

Questions about these assertions arose in the following manner. Beineke 123 proved that a graph G is the line graph of some graph H iff G does not induce any of the graphs G1, . . . , G9 depicted in Fig. 1.

If G is the line graph of H, then x'(H) = x(G) and, provided that A(H) 2 3, A(H) = o(G). Thus Vizing's Theorem [8] for graphs can be stated as follows: if G is a graph that does not induce any of the graphs G1,. . . , G9, then x(G)< o(G) + 1. Choudum [3] showed that the conclusion holds either if G does not induce any of the graphs G1, Ga, G3, or G4, or if G does not induce ;;ny of the graphs G1, G?, G5 or Gg. Javdekar [Sj improved this result by eliminatiug G3 and G, from the hypothesis and conjectured that for all n, C(n) is true. In this paper we shall prove that for all n, C(n) is true iff C'(U) is true, thus returning Javdekar's conjecture to the domain of edge coloring. EartIer Jakobsen [6] had