×

Complexity of approximation of 3-edge-coloring of graphs. (English) Zbl 1191.68468

Summary: 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(n^{1-\varepsilon })\), where \(n\) denotes the order of the graph and \(0<\varepsilon <1\) is a constant.

MSC:

68R10 Graph theory (including graph drawing) in computer science
68W25 Approximation algorithms
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Garey, M. R.; Johnson, D. S., Computers and Intractability (1979), W.H. Freeman: W.H. Freeman San Francisco · Zbl 0411.68039
[2] Holyer, I., The NP-completeness of edge-coloring, SIAM J. Comput., 10, 718-720 (1981) · Zbl 0473.68034
[3] Isaacs, R., Infinite families of nontrivial trivalent graphs which are not Tait colorable, Amer. Math. Monthly, 82, 221-239 (1975) · Zbl 0311.05109
[4] Jaeger, F.; Swart, T., Conjecture 2, (Deza, M.; Rosenberg, I. G., Combinatorics 79. Combinatorics 79, Ann. Discrete Math., vol. 9 (1980), North-Holland: North-Holland Amsterdam), 305
[5] Kochol, M., A cyclically 6-edge-connected snark of order 118, Discrete Math., 161, 297-300 (1996) · Zbl 0870.05025
[6] Kochol, M., Superposition and constructions of graphs without nowhere-zero \(k\)-flows, European J. Combin., 23, 281-306 (2002) · Zbl 1010.05062
[7] Kochol, M.; Krivoňáková, N.; Smejová, S., Approximation algorithm for chromatic index and edge-coloring of multigraphs, (Nikoletseas, S. E., Experimental and Efficient Algorithms. Experimental and Efficient Algorithms, Lecture Notes in Comput. Sci., vol. 3503 (2005), Springer-Verlag: Springer-Verlag Berlin), 602-605 · Zbl 1121.68468
[8] Vizing, V. G., On an estimate of the chromatic class of a \(p\)-graph, Diskret. Analiz, 3, 25-30 (1964), (in Russian)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.