Applications of edge coloring of multigraphs to vertex coloring of graphs (Q1121898): Difference between revisions

If G is a graph which induces neither \(K_{1,3}\) nor \(K_{2s+3}-e\), and the maximum clique size \(\omega\) (G) is sufficiently large then \(\chi (G)\leq \omega (G)+s.\) The proof relies on showing a correspondence between vertex coloring G and edge coloring a certain multigraph and then applying a previous result on edge coloring. The author hopes that his work will stimulate research on edge coloring multigraphs by showing how chromatic index bounds for multigraphs can be used to derive results on chromatic number. A number of interesting problems and conjectures are also proposed.