DP-completeness of exact circular chromatic index

Let r3r\ge 3 be a rational number. For a graph GG, let χc(G)\chi_c'(G) denote its circular chromatic index, and let CCHI=r\mathrm{CCHI}^{=_r} be the decision problem of determining whether χc(G)=r\chi_c'(G)=r.

DP-completeness conjecture. The problem CCHI=r\mathrm{CCHI}^{=_r} is DP-complete.

The preceding complexity discussion establishes NP-completeness for deciding whether χc(G)r\chi_c'(G)\le r 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

No solutions have been posted yet.