The interval constrained 3-coloring problem

DOI10.1007/978-3-642-12200-2_51zbMATH Open1283.05083arXiv0907.3563OpenAlexW2899328677MaRDI QIDQ3557052FDOQ3557052

Authors: Jaroslaw Byrka, Andreas Karrenbauer, Laura Sanità 

Publication date: 27 April 2010

Published in: LATIN 2010: Theoretical Informatics (Search for Journal in Brave)

Abstract: In this paper, we settle the open complexity status of interval constrained coloring with a fixed number of colors. We prove that the problem is already NP-complete if the number of different colors is 3. Previously, it has only been known that it is NP-complete, if the number of colors is part of the input and that the problem is solvable in polynomial time, if the number of colors is at most 2. We also show that it is hard to satisfy almost all of the constraints for a feasible instance.

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

Recommendations

• The interval constrained 3-coloring problem
• On the approximability of the maximum interval constrained coloring problem
• Deconstructing intractability-A multivariate complexity analysis of interval constrained coloring
• Deconstructing Intractability: A Case Study for Interval Constrained Coloring
• On the approximability of the maximum interval constrained coloring problem

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coloring of graphs and hypergraphs (05C15)

Cited In (7)

• On the approximability of the maximum interval constrained coloring problem
• Deconstructing intractability-A multivariate complexity analysis of interval constrained coloring
• On the approximability of the maximum interval constrained coloring problem
• 3-coloring arrangements of line segments with 4 slopes is hard
• Deconstructing Intractability: A Case Study for Interval Constrained Coloring
• Choice is hard
• The interval constrained 3-coloring problem

This page was built for publication: The interval constrained 3-coloring problem

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