When the Vertex Coloring of a Graph is an Edge Coloring of its Line Graph — A Rare Coincidence

Abstract

The \(3\)-consecutive vertex coloring number \(\psi_{3c}(G)\) of a graph \(G\) is the maximum number of colors permitted in a coloring of the vertices of \(G\) such that the middle vertex of any path \(P_3\) in \(G\) has the same color as one of the ends of that \(P_3\). This coloring constraint exactly means that no \(P_3\) subgraph of \(G\) is properly colored in the classical sense. The \(3\)-consecutive edge coloring number \(\psi’_{3c}\) is the maximum number of colors permitted in a coloring of the edges of \(G\) such that the middle edge of any sequence of three edges (in a path \(P_3\) or cycle \(C_3\)) has the same color as one of the other two edges. For graphs \(G\) of minimum degree at least \(2\), denoting by \(L(G)\) the line graph of \(G\), we prove that there is a bijection between the \(3\)-consecutive vertex colorings of \(G\) and the \(3\)-consecutive edge colorings of \(L(G)\), which keeps the number of colors unchanged, too. This implies that \(\psi_{3c} = \psi’_{3c}(L(G))\); i.e., the situation is just the opposite of what one would expect at first sight.