Complexity of approximation of 3-edge-coloring of graphs |
| |
Authors: | Martin Kochol Nad'a Krivoňáková |
| |
Affiliation: | a MÚ SAV, Štefánikova 49, 814 73 Bratislava 1, Slovakia b FPV ?U, Hurbanova 15, 010 26 ?ilina, Slovakia |
| |
Abstract: | The problem to find a 4-edge-coloring of a 3-regular graph is solvable in polynomial time but an analogous problem for 3-edge-coloring is NP-hard. To make the gap more precise, we study complexity of approximation algorithms for invariants measuring how far is a 3-regular graph from having a 3-edge-coloring. We show that it is an NP-hard problem to approximate such invariants with an error O(n1−ε), where n denotes the order of the graph and 0<ε<1 is a constant. |
| |
Keywords: | Edge-coloring of graphs NP-completeness Approximation algorithms Cyclical edge-connectivity |
本文献已被 ScienceDirect 等数据库收录! |