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

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 is an element of E so that adjacent edges get different colors. A k-edge-coloring is linear compact if the colors on the edges 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 for every vertex v there are two positive integers a(v), b(v) in {0, 1, ... , k - 1} such that the colors on the edges incident to v are exactly {a(v), (a(v) + 1)mod k, ..., b(v)}. 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. (C) 2011 Elsevier B.V. All rights reserved.