A new color change to improve the coloring of a graph

DOI10.1016/0166-218X(92)90268-FMaRDI QIDQ5893808zbMATH OpenFDO

Authors C. Berge

Publication date 1989

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0166-218X(92)90268-F

zbMATH Keywords

color interchangesoptimal colouringproper vertex colouringsVizing's theorem

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Review text

The colourings under consideration are proper vertex colourings of simple graphs. A q-colouring is a vertex colouring using exactly q colours. Any two adjacent vertices receive different colours. Let \(G=(X,E)\) be a simple graph with the vertex set X and \(x_ 0\in X\). Suppose, there is a q-colouring for the subgraph of G induced by \(X- \{x_ 0\}\). The main result of the paper is a necessary and sufficient condition for G to be q-colourable, where a basic tool is the consideration of alternating sequences of vertices. A simplified construction of 3-colourings is given for graphs without an induced \(K_{1,3}.\) The question if the main result allows to simplify the proof of Vizing's well-known theorem is still open.

Recommendations

• A new graph coloring scheme
• A new kind of graph coloring
• Improved dynamic graph coloring
• Improved dynamic graph coloring
• Graph colouring variations
• scientific article; zbMATH DE number 1161310
• scientific article; zbMATH DE number 6863765
• New tools for graph coloring
• scientific article; zbMATH DE number 7759285
• Graph colouring and variations

Cited in

(1)

• scientific article; zbMATH DE number 3926942 (Why is no real title available?)

This page was built for publication: A new color change to improve the coloring of a graph

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