Group for Research in Decision Analysis

On Compact k-Edge-Colorings: A Polynomial Time Reduction From Linear to Cyclic

Sivan Altinakar, Gilles Caporossi, and Alain Hertz

A k-edge-coloring of a graph G=(V,E) is a function c that assigns an integer c(e) (called color) in {0,1, ..., k-1} to every edge e in E so that adjacent edges get different colors. A k-edge-coloring is linear compact if the colors incident to every vertex are consecutive. The problem k-LCCP is to determine whether a given graph admits a linear compact k-edge coloring. A k-edge-coloring is cyclic compact if there are two positive integers av, bv in {0,1, ..., k-1} for every vertex v such that the colors incident to v are exactly {av, (av+1) mod k, ..., bv}. The problem k-CCCP is to determine whether a given graph admits a cyclic compact k-edge coloring. We show that the k-LCCP with possibly imposed or forbidden colors on some edges is polynomially reducible to the k-CCCP when k >= 12, and to the 12-CCCP when k<12.

, 19 pages