Reducibility reformulation of McDiarmid–Reed's conjecture

Let GG be a hexagonal graph, and let F9,4\mathcal{F}_{9,4} and F9,4\mathcal{F}'_{9,4} be the families of (9,4)(9,4)-reducible H-handles used in the paper. Write coreF9,4F9,4(G)\operatorname{core}_{\mathcal{F}_{9,4}\cup\mathcal{F}'_{9,4}}(G) for the graph obtained after reducing GG by these configurations.

McDiarmid–Reed reducibility conjecture. For every hexagonal graph GG, coreF9,4F9,4(G)\operatorname{core}_{\mathcal{F}_{9,4}\cup\mathcal{F}'_{9,4}}(G) is (9,4)(9,4)-colorable.

The statement is presented as an equivalent form of McDiarmid–Reed's conjecture. The paper's new reductions substantially decrease the number of irreducible configurations found computationally, but some configurations remain and no proof is given.

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.