### G-2009-53

# 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 *a _{v}, b_{v}* in

*{0,1, ..., k-1}*for every vertex

*v*such that the colors incident to

*v*are exactly

*{a*mod

_{v}, (a_{v}+1)*k, ..., b*. The problem

_{v}}*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*.

Published **September 2009**
,
19 pages