Weak diameter 2-coloring near non-triangular faces
Question 6 · arXiv:2111.07147
Status open high confidence
No follow-up paper resolving Question 6 was found in the indexed literature. The conjecture asks whether the class G_r of plane graphs with no separating triangles, where each vertex is within distance r of a face of length at least four, has weak diameter chromatic number at most two. The authors note a positive answer in the special case of graphs with exactly one non-triangular face (bounded treewidth implies asymptotic dimension one). The source paper was published in the European Journal of Combinatorics (2023), and a related 2023 preprint (arXiv:2310.17795) extends weak-diameter choosability to excluded-minor classes but does not address this specific planar question.
Reviewer notes. No follow-up found specifically addressing Question 6. The most closely related post-2021 work is arXiv:2310.17795 (Crouch and Liu, 2023) on weak diameter choosability for excluded-minor graphs, which does not treat the G_r class. The conjecture is recent (2021) and the absence of resolution in a wide web search supports open status with high confidence.
Context
The authors suspect that a substantial relaxation of the triangle-free assumption is sufficient to allow coloring by two colors. They note that the HEX-lemma-based example with triangulated grids shows that non-triangular faces are essential, and remark that the question has a positive answer in the special case where the graph has exactly one non-triangular face (since proximity to a fixed face forces bounded treewidth and hence asymptotic dimension one).
Source paper
Weak diameter coloring of graphs on surfaces
Zdeněk Dvořák, Sergey Norin · 2021-11-13
https://arxiv.org/abs/2111.07147
PDF source