### Abstract

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.

Original language | English |
---|---|

Title of host publication | Algorithms and Computation - 21st International Symposium, ISAAC 2010, Proceedings |

Pages | 132-143 |

Number of pages | 12 |

Edition | PART 2 |

DOIs | |

Publication status | Published - Dec 1 2010 |

Event | 21st Annual International Symposium on Algorithms and Computations, ISAAC 2010 - Jeju Island, Korea, Republic of Duration: Dec 15 2010 → Dec 17 2010 |

### Publication series

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

Number | PART 2 |

Volume | 6507 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

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

Country | Korea, Republic of |

City | Jeju Island |

Period | 12/15/10 → 12/17/10 |

### Fingerprint

### ASJC Scopus subject areas

- Theoretical Computer Science
- Computer Science(all)

### Cite this

*Algorithms and Computation - 21st International Symposium, ISAAC 2010, Proceedings*(PART 2 ed., pp. 132-143). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6507 LNCS, No. PART 2). https://doi.org/10.1007/978-3-642-17514-5_12