Summary: It was conjectured in [\textit{S. Akbari}, \textit{F. Khaghanpoor}, and \textit{S. Moazzeni}, ``Colorful paths in vertex coloring of graphs, Preprint] that, if \(G\) is a connected graph distinct from \(C_7\), then there is a \(\chi(G)\)-coloring of \(G\) in which every vertex \(v \in V(G)\) is an initial vertex of a path \(P\) with \(\chi(G)\) vertices whose colors are different. In [\textit{S. Akbari}, \textit{V. Liaghat}, and \textit{A. Nikzad}. ``Colorful paths in vertex coloring of graphs, Electron. J. Comb. 18, No.\,1, Research Paper P17, 9 p., electronic only (2011; Zbl 1290.05070)] this was proved with \(\left\lfloor \frac{\chi (G)}{2} \right\rfloor \) vertices instead of \(\chi (G)\) vertices. We strengthen this to \(\chi (G) - 1\) vertices. We also prove that every connected graph with at least one edge has a proper \(k\)-coloring (for some \(k\)) such that every vertex of color \(i\) has a neighbor of color \(i + 1 (\text{mod} k)\). \(C_5\) shows that \(k\) may have to be greater than the chromatic number. However, if the graph is connected, infinite and locally finite, and has finite chromatic number, then the \(k\)-coloring exists for every \(k \geq \chi(G)\). In fact, the \(k\)-coloring can be chosen such that every vertex is a starting vertex of an infinite path such that the color increases by \(1 (\text{mod} k)\) along each edge. The method is based on the circular chromatic number \(\chi c(G)\). In particular, we verify the above conjecture for all connected graphs whose circular chromatic number equals the chromatic number.
- A note on the Gallai-Roy-Vitaver theorem
- Optimal colorings with rainbow paths
- Chromatic layout number of paths and cycles
- A colourful path
- scientific article; zbMATH DE number 653270 (Why is no real title available?)
- Colorful paths for 3-chromatic graphs
- Colorings of complements of line graphs
- Dynamic chromatic number of regular graphs
This page was built for publication: Rainbow paths with prescribed ends
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q540082)
