On compact \(k\)-edge-colorings: a polynomial time reduction from linear to cyclic (Q666002): Difference between revisions

A \(k\)-edge-coloring of a graph assigns an integer \(0,\dots,k-1\) to each edge such that adjacent edges receive distinct colors. It is linear compact if the colors on the edges adjacent to every vertex are consecutive. Linear compact colorings have also been called consecutive edge-colorings and interval edge-colorings. A \(k\)-edge-coloring is cyclic compact if the colors at a vertex are consecutive when read modulo \(k\). The \(k\)-{LCCP} (\(k\)-{CCCP}) is to determine if a given graph has a linear compact \(k\)-edge coloring (cyclic compact edge-coloring resp.). Both problems are \textit{NP}-complete. The authors show that the \(k\)-{LCCP} with possibly imposed or forbidden colors on some edges is polynomially reducible to the \(k\)-{CCCP} when \(k \geq 12\) and to the 12-{CCCP} when \(k < 12\).