TY - GEN

T1 - Approximation and hardness results for the maximum edge q-coloring problem

AU - Adamaszek, Anna

AU - Popa, Alexandru

N1 - Funding Information:
Acknowledgements. We would like to thank to Artur Czumaj and Nigel Smart for their useful comments. The second author is funded by an EPSRC PhD studentship.
Funding Information:
★ Research supported in part by the Centre for Discrete Mathematics cations (DIMAP), EPSRC award EP/D063191/1.

PY - 2010

Y1 - 2010

N2 - We consider the problem of coloring edges of a graph subject to the following constraint: for every vertex v, all the edges incident to v have to be colored with at most q colors. The goal is to find a coloring satisfying the above constraint and using the maximum number of colors. This problem has been studied in the past from the combinatorial and algorithmic point of view. The optimal coloring is known for some special classes of graphs. There is also an approximation algorithm for general graphs, which in the case q = 2 gives a 2-approximation. However, the complexity of finding the optimal coloring was not known. We prove that for any integer q ≥ 2 the problem is NP-Hard and APX-Hard. We also present a 5/3-approximation algorithm for q = 2 for graphs with a perfect matching.

AB - We consider the problem of coloring edges of a graph subject to the following constraint: for every vertex v, all the edges incident to v have to be colored with at most q colors. The goal is to find a coloring satisfying the above constraint and using the maximum number of colors. This problem has been studied in the past from the combinatorial and algorithmic point of view. The optimal coloring is known for some special classes of graphs. There is also an approximation algorithm for general graphs, which in the case q = 2 gives a 2-approximation. However, the complexity of finding the optimal coloring was not known. We prove that for any integer q ≥ 2 the problem is NP-Hard and APX-Hard. We also present a 5/3-approximation algorithm for q = 2 for graphs with a perfect matching.

UR - http://www.scopus.com/inward/record.url?scp=78650963895&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=78650963895&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-17514-5_12

DO - 10.1007/978-3-642-17514-5_12

M3 - Conference contribution

AN - SCOPUS:78650963895

SN - 3642175163

SN - 9783642175169

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 132

EP - 143

BT - Algorithms and Computation - 21st International Symposium, ISAAC 2010, Proceedings

T2 - 21st Annual International Symposium on Algorithms and Computations, ISAAC 2010

Y2 - 15 December 2010 through 17 December 2010

ER -