A new color change to improve the coloring of a graph (Q5893808)

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.