| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4652904 | Electronic Notes in Discrete Mathematics | 2007 | 5 Pages |
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. We study complexity of approximation algorithms for invariants measuring how far is a 3-regular graph from having a 3-edge-coloring. We prove that it is an NP-hard problem to approximate such invariants by a power function with exponent smaller than 1.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
