Exact-Mk-Colorability: A Study in Graph Coloring Complexity

Title: Exact-Mk-Colorability: A Study in Graph Coloring Complexity

Abstract: This research explores the complexity of determining whether a graph can be colored using a specific number of colors, known as Exact-Mk-Colorability. The study focuses on the case where Mk is a set of consecutive integers. The main question addressed is: For a given k, what is the smallest number of colors in Mk such that Exact-Mk-Colorability is still computationally challenging?

The research uses the boolean hierarchy over NP, a framework for classifying problems based on their complexity. It shows that for k = 1, it is DP-complete (a higher level of complexity) to determine whether χ(G) = 4, but Exact-{3}-Colorability is in NP (a lower level of complexity). This result solves a long-standing question in the field of graph theory.

The study also provides a general solution for all k ≥ 1, showing that Exact-Mk-Colorability is BH 2k(NP)-complete for Mk = {3k + 1, 3k + 3, ..., 5k - 1}. This means that for any given k, the problem of determining whether a graph can be colored using the colors in Mk is computationally challenging.

Implications: This research has significant implications for the field of graph theory and complexity theory. It provides a better understanding of the complexity of graph coloring problems and may lead to new algorithms and techniques for solving these problems. Additionally, the results may have applications in other areas of computer science and mathematics that involve similar types of problems.

Keywords: Graph coloring, complexity theory, boolean hierarchy, NP-completeness, DP-completeness

Link to Article: https://arxiv.org/abs/0109018v1 Authors: arXiv ID: 0109018v1