DP-completeness of exact circular chromatic index

Less than 1 year old · traced to

Let r≥3r\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.

References

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.