Approximating Maximum Edge 2-Coloring by Normalizing Graphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916720836345856 |
|---|---|
| author | Mömke, Tobias Popa, Alexandru Roshany-Tabrizi, Aida Ruderer, Michael Vincze, Roland |
| author_facet | Mömke, Tobias Popa, Alexandru Roshany-Tabrizi, Aida Ruderer, Michael Vincze, Roland |
| contents | In a simple, undirected graph G, an edge 2-coloring is a coloring of the edges such that no vertex is incident to edges with more than 2 distinct colors. The problem maximum edge 2-coloring (ME2C) is to find an edge 2-coloring in a graph G with the goal to maximize the number of colors. For a relevant graph class, ME2C models anti-Ramsey numbers and it was considered in network applications. For the problem a 2-approximation algorithm is known, and if the input graph has a perfect matching, the same algorithm has been shown to have a performance guarantee of 5/3. It is known that ME2C is APX-hard and that it is UG-hard to obtain an approximation ratio better than 1.5. We show that if the input graph has a perfect matching, there is a polynomial time 1.625-approximation and if the graph is claw-free or if the maximum degree of the input graph is at most three (i.e., the graph is subcubic), there is a polynomial time 1.5-approximation algorithm for ME2C |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_06691 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Approximating Maximum Edge 2-Coloring by Normalizing Graphs Mömke, Tobias Popa, Alexandru Roshany-Tabrizi, Aida Ruderer, Michael Vincze, Roland Discrete Mathematics Data Structures and Algorithms In a simple, undirected graph G, an edge 2-coloring is a coloring of the edges such that no vertex is incident to edges with more than 2 distinct colors. The problem maximum edge 2-coloring (ME2C) is to find an edge 2-coloring in a graph G with the goal to maximize the number of colors. For a relevant graph class, ME2C models anti-Ramsey numbers and it was considered in network applications. For the problem a 2-approximation algorithm is known, and if the input graph has a perfect matching, the same algorithm has been shown to have a performance guarantee of 5/3. It is known that ME2C is APX-hard and that it is UG-hard to obtain an approximation ratio better than 1.5. We show that if the input graph has a perfect matching, there is a polynomial time 1.625-approximation and if the graph is claw-free or if the maximum degree of the input graph is at most three (i.e., the graph is subcubic), there is a polynomial time 1.5-approximation algorithm for ME2C |
| title | Approximating Maximum Edge 2-Coloring by Normalizing Graphs |
| topic | Discrete Mathematics Data Structures and Algorithms |
| url | https://arxiv.org/abs/2403.06691 |