Article ID Journal Published Year Pages File Type
1141653 Discrete Optimization 2011 11 Pages PDF
Abstract

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

Related Topics
Physical Sciences and Engineering Mathematics Control and Optimization
Authors
, , ,