Odd-girth multicoloring conjecture for hexagonal graphs

Let k1k\geq 1, and let GG be a hexagonal graph, meaning a finite triangle-free induced subgraph of the triangular lattice. The odd-girth of GG is the length of its shortest odd cycle.

Odd-girth multicoloring conjecture. If GG has odd-girth at least 2k+12k+1, then GG is (2k+1,k)(2k+1,k)-colorable.

This conjecture generalizes McDiarmid–Reed's conjecture and is proposed as a possible extension of the paper's results. The source does not provide a proof or a resolution.

Sources & referencesView supporting material

Primary source

Jean-Christophe Godin and Olivier Togni, “New reducible configurations for graph multicoloring with application to the experimental resolution of McDiarmid-Reed's Conjecture (extended version)”, arXiv:1812.01911 (2023).

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.