NP-completeness of coloring finite distance graphs
Let be a finite set of positive integers, and let denote the chromatic number of the distance graph with distance set . For a fixed integer , consider the decision problem of determining whether . NP-completeness conjecture. Determining whether for finite sets is NP-complete. This conjecture extends the known NP-completeness of deciding whether the chromatic number of a finite graph is at most ; the paper notes that an algorithm exists for computing when is finite, but leaves the efficiency of that algorithm unresolved.
References
- Glenn G. Chappell, “Coloring Distance Graphs on the Integers”, arXiv:math/9805084 (1998).
Progress summary
Never refreshed
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.