Approximation of 3-Edge-Coloring of Cubic Graphs |
| |
| Institution: | 1. Department of Mathematics, Southwestern University of Finance and Economics, Chengdu 611130, China;2. School of Mathematical Sciences, University of Science and Technology of China, Wentsun Wu Key Laboratory of CAS, Hefei 230026, China |
| |
| 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. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
