Circular coloring triangle-free subcubic planar graphs
Status open medium confidence
The problem of whether every triangle-free planar graph of maximum degree three satisfies $\chi_c(G) \leq 20/7$ remains open as of all accessible literature. The bound is tight: the dodecahedron belongs to this class and achieves $\chi_c = 20/7$. No proof or counterexample was found in the literature reachable by web search and verified fetch.
Reviewer notes. Zhu's personal open-problems status page (math.nsysu.edu.tw/~zhu/open-problems/status.htm and chic-k3free-planar.htm) returned TLS certificate errors and could not be fetched; it may contain updates. The OPG page itself was also unreachable (ECONNREFUSED). The paper arXiv:2204.12683 (Dvořák et al., 2022/2025) establishes $\chi_f(G) \leq 11/4$ for subcubic triangle-free graphs (up to two exceptions including the Petersen graph; the dodecahedron likely being a second exception with $\chi_f = \chi_c = 20/7$), but this concerns the fractional chromatic number — a different and weaker parameter since $\chi_f \leq \chi_c$ — and does not resolve the circular coloring question. No arXiv papers combining all three key terms (circular chromatic, triangle-free, planar, subcubic/degree-3) were returned by any search.
Discussion
Throughout, we let $ \chi_c(G) $ denote the circular chromatic number of the graph $ G $ . A well-known Question of Nesetril asks if $ \chi_c(G) \le \frac{5}{2} $ for all cubic graphs $ G $ of sufficiently high girth. A conjecture of Jaeger asserts that $ \chi_c(G) \le 2 + \frac{1}{k} $ for every planar graph $ G $ of girth $ 4k+1 $ . There are numerous partial results on these problems, and there are many interesting questions concerning the circular chromatic numbers of restricted families of graphs. Here we are restricted to planar graphs of girth $ \ge 4 $ with maximum degree $ \le 3 $ . The dodecahedron lives in this class and has $ \chi_c = \frac{20}{7} $ . It remains unclear if anyone else in this class might have $ \chi_c $ larger. A related conjecture of X. Zhu asserts that for every triangle-free planar graph $ G $ with $ \Delta(G)\le 4 $ and $ |V(G)|<3k $ one has $ \chi_c(G)\le 3-1/k $ .