Graph-theory open problems

Modular chromatic index of 0ₖ-graphs

Conjecture 13 · arXiv:2507.04254

arXiv Conjecture high confidence— first stated 2025-12-05
Authors: Gaétan Berthe, Marthe Bonamy, Fábio Botler, Gaia Carenini, Lucas Colucci, Arthur Dumas, Fatemeh Ghasemi, Pedro Mariano Viana Neto

Status open high confidence

Conjecture 13 from arXiv:2507.04254 asserts that every $0_k$-graph $G$ satisfies $\chi'_k(G) \leq k + o(k)$, which would match the lower bound and close the gap in the main result of the paper. The source paper itself improves the general upper bound to $\chi'_k(G) \leq 9k$; the conjecture, if true, would yield $\chi'_k(G) \leq k + o(k)$ for all graphs as a corollary via their proof strategy. No follow-up work resolving or partially resolving this specific conjecture was found in the indexed literature as of May 2026.

Reviewer notes. The conjecture was introduced in December 2025 and no follow-up paper addressing it was found after three targeted web searches and two WebFetch verifications. The related paper arXiv:2510.04334 (on modular chromatic index of random hypergraphs) predates the source and does not address Conjecture 13.

Auto-reviewed 2026-05-14 with claude-sonnet-4-6 (web search enabled).

Conjecture. Let $k$ be a positive integer. For every $0_{k}$-graph $G$ we have $\chi^{\prime}_{k}(G)\leq k+o(k)$.

Context

A $0_k$-graph is a graph whose relevant subgraph structure satisfies a $0\pmod{k}$ degree condition. If Conjecture 13 holds, the proof strategy of Theorem 2 can be adapted so that a maximal $0_k$-subgraph $H$ of any graph $G$ is coloured with $\leq k+o(k)$ colours and the remainder (which would then be $(2q(k)-2)$-degenerate) is coloured via Lemma 9, yielding an overall bound approaching $\chi^{\prime}_{k}(G)\leq k+o(k)$ for all graphs.

Also stated in

Source paper

On Modular Edge Colourings of Graphs
Gaétan Berthe, Marthe Bonamy, Fábio Botler, Gaia Carenini, Lucas Colucci, Arthur Dumas, Fatemeh Ghasemi, Pedro Mariano Viana Neto · 2025-12-05
https://arxiv.org/abs/2507.04254