Mixed-parity components in disconnected 4-coloring complexes
Conjecture 8 · arXiv:1912.07205
Status open high confidence
Conjecture 8 from arXiv:1912.07205 (Mohar and Singer, published in European Journal of Combinatorics 2021) asserts that every planar triangulation with a disconnected 4-coloring complex must contain at least one even-parity and one odd-parity component. The conjecture was posed as an open problem based on extensive computation, after the paper resolved Tutte's original question by constructing planar triangulations with arbitrarily many same-parity components. No follow-up work resolving this conjecture was found in the indexed literature through May 2026.
Reviewer notes. The source paper was published as: European Journal of Combinatorics, vol. 91 (2021), article 103221, DOI:10.1016/j.ejc.2020.103221. A thematically adjacent paper arXiv:2101.04065 (Kempe equivalence of 4-critical planar graphs, showing every 4-critical planar graph has its 4-colorings forming a single Kempe class) was found but addresses a different structural question and does not directly resolve Conjecture 8. No follow-up found in indexed literature.
Context
After resolving Tutte's original question by constructing triangulations with arbitrarily many same-parity components, the authors identify this closely related conjecture based on extensive computation. It refines the picture by asserting that disconnected coloring complexes always contain both parities.
Notes. The conjecture is described verbatim in both the abstract and the introduction with a forward reference to 'Conjecture 8', but the formal conjecture environment itself is not present in the extracted PDF text (the paper body appears truncated after Section 5). Statement reconstructed from the abstract and introduction prose.
Source paper
The Last Temptation of William T. Tutte
Bojan Mohar, Nathan Singer · 2019-12-16
https://arxiv.org/abs/1912.07205
PDF source