On compact k-edge-colorings: a polynomial time reduction from linear to cyclic

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\).

Recommendations

Cites work

Cited in

(3)

This page was built for publication: On compact \(k\)-edge-colorings: a polynomial time reduction from linear to cyclic

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