DP-completeness of exact circular chromatic index
DP-completeness of exact circular chromatic index
Let be a rational number. For a graph , let denote its circular chromatic index, and let be the decision problem of determining whether .
DP-completeness conjecture. The problem is DP-complete.
The preceding complexity discussion establishes NP-completeness for deciding whether and explains why exact equality also involves a coNP component; the claimed DP-completeness is proposed on that basis.
Sources & referencesView supporting material
Primary source
Ján Mazák and Filip Zrubák, “Circular chromatic index of small graphs”, arXiv:2603.08822 (2026).
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
Sign in to submit a solution.
No solutions have been posted yet.