Fractional 3-coloring of triangle-free planar requests

Problem 1 · arXiv:1702.00588

arXiv Problem high confidence— first stated 2017-09-19

Authors: Zdeněk Dvořák, Jean-Sébastien Sereni

Status disproved medium confidence

The source paper (1702.00588) proves in Theorem 1 that Problem 1 (RGEN: existence of \alpha>0 such that every planar triangle-free request graph admits a 3-coloring satisfying an \alpha-fraction of its requests) is equivalent to Thomassen's conjecture (EXP: every planar triangle-free graph on n vertices has at least 2^{\beta n} 3-colorings for some \beta>0). EXP has since been disproved: Dvo\v{r}\'{a}k (arXiv:2108.12669, 2021) constructs planar triangle-free graphs with at most 2^{6n^{0.731}} 3-colorings (sub-exponential), improving on Thomassen's own earlier counterexample to his conjecture. By the equivalence RGEN \Leftrightarrow EXP, no positive real \alpha of the type sought in Problem 1 can exist.

Cited literature (2)

partial Flexibility of triangle-free planar graphs (2021)

Dvo\v{r}\'{a}k, Z., Masa\v{r}\'{i}k, T., Mus\'{i}lek, J., Pangr\'{a}c, O. · Journal of Graph Theory · arXiv:1902.02971 · doi:10.1002/jgt.22634

For a related list-4-coloring setting, proves that every triangle-free planar graph with all lists of size at least 4 admits an L-coloring satisfying a constant fraction of vertex color preferences; does not directly resolve the 3-coloring request graph formulation of Problem 1.
counterexample Triangle-free planar graphs with at most 64^{n^{0.731}} 3-colorings (2021)

Dvo\v{r}\'{a}k, Z. · arXiv preprint · arXiv:2108.12669

Constructs planar triangle-free graphs with sub-exponentially many 3-colorings, disproving Thomassen's EXP conjecture; since RGEN \Leftrightarrow EXP by Theorem 1 of the source paper, this indirectly disproves Problem 1.

Reviewer notes. The disproof of Problem 1 is indirect: no paper provides an explicit counterexample to a request graph instance, but the logical chain is rigorous since RGEN \Leftrightarrow EXP is Theorem 1 of the source paper and EXP is disproved by 2108.12669 (and an earlier, unverified counterexample by Thomassen himself). The doi 10.1002/jgt.22634 for 1902.02971 is inferred from the Wiley Online Library URL in search results (direct fetch returned HTTP 402). The flexibility result (1902.02971) represents a positive partial result for a related but strictly different problem.

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

Problem. Is there a positive real number $\alpha$ such that every planar triangle-free request graph admits a 3-coloring satisfying $\alpha$-fraction of its requests?

Context

This problem arises from the work of Asadi et al. [1] and is introduced as a reformulation vehicle for Thomassen's exponential-coloring conjecture. A request graph $(G, R_=, R_{\neq}, w)$ consists of a planar triangle-free graph $G$ together with degree-two vertices partitioned into equality requests $R_=$ and inequality requests $R_{\neq}$ with positive rational weights; a coloring satisfies a request if the two neighbors receive equal (resp. different) colors.

Source paper

Do triangle-free planar graphs have exponentially many 3-colorings?
Zdeněk Dvořák, Jean-Sébastien Sereni · 2017-09-19
https://arxiv.org/abs/1702.00588 PDF source