Applications of edge coloring of multigraphs to vertex coloring of graphs

DOI10.1016/0012-365X(89)90203-3MaRDI QIDQ1121898zbMATH OpenOpenAlexFDO

Authors H. A. Kierstead

Publication date 1989

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365x(89)90203-3

zbMATH Keywords

chromatic indexchromatic numbermultigraph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Review text

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.

Recommendations

• A note concerning the chromatic index of multigraphs
• On the chromatic number of a graph with two forbidden subgraphs
• On the chromatic index of multigraphs without large triangles
• Edge coloring multigraphs without small dense subsets
• The chromatic number of graphs which induce neither \(K_{1,3}\) nor \(K_ 5-e\)

Cites work

• A Theorem on Coloring the Lines of a Network
• CHROMATIC BOUNDS FOR A CLASS OF GRAPHS
• Edge-coloring of multigraphs: Recoloring technique
• Graph Theory and Probability
• scientific article; zbMATH DE number 3747156 (Why is no real title available?)
• scientific article; zbMATH DE number 3480625 (Why is no real title available?)
• scientific article; zbMATH DE number 3286813 (Why is no real title available?)
• scientific article; zbMATH DE number 3043302 (Why is no real title available?)
• Multicoloring the incidentors of a weighted directed multigraph
• Note on Choudum's “chromatic bounds for a class of graphs”
• On edge-colorings of graphs.
• On Multi-Colourings of Cubic Graphs, and Conjectures of Fulkerson and Tutte
• On the chromatic index of multigraphs without large triangles
• Some applications of Vizing's theorem to vertex colorings of graphs
• The chromatic number of graphs which induce neither \(K_{1,3}\) nor \(K_ 5-e\)
• The NP-Completeness of Edge-Coloring

Cited in

(3)

• Claw-free graphs---a survey
• Colouring squares of claw-free graphs
• Colouring squares of claw-free graphs

This page was built for publication: Applications of edge coloring of multigraphs to vertex coloring of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1121898)