The hardness of the functional orientation 2-color problem

zbMATH Open1278.68102arXiv1210.2544MaRDI QIDQ2848741FDOQ2848741

Authors: Søren Bøg, Morten Stöckel, Hjalte Wedel Vildhøj 

Publication date: 26 September 2013

Published in: The Australasian Journal of Combinatorics (Search for Journal in Brave)

Abstract: We consider the Functional Orientation 2-Color problem, which was introduced by Valiant in his seminal paper on holographic algorithms [SIAM J. Comput., 37(5), 2008]. For this decision problem, Valiant gave a polynomial time holographic algorithm for planar graphs of maximum degree 3, and showed that the problem is NP-complete for planar graphs of maximum degree 10. A recent result on defective graph coloring by Corr^ea et al. [Australas. J. Combin., 43, 2009] implies that the problem is already hard for planar graphs of maximum degree 8. Together, these results leave open the hardness question for graphs of maximum degree between 4 and 7. We close this gap by showing that the answer is always yes for arbitrary graphs of maximum degree 5, and that the problem is NP-complete for planar graphs of maximum degree 6. Moreover, for graphs of maximum degree 5, we note that a linear time algorithm for finding a solution exists.

Full work available at URL: https://arxiv.org/abs/1210.2544

Recommendations

• Oriented coloring in planar, bipartite, bounded degree 3 acyclic oriented graphs
• SOFSEM 2006: Theory and Practice of Computer Science
• The complexity of the proper orientation number
• Orientations of graphs with prescribed weighted out-degrees
• Computational complexity of \((2,2)\) path chromatic number problem

zbMATH Keywords

2-color problemfunctional orientation

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Applications of graph theory to circuits and networks (94C15)

Cited In (1)

• Orientations of graphs with prescribed weighted out-degrees

This page was built for publication: The hardness of the functional orientation 2-color problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2848741)