Abstract
DP-coloring was introduced by Dvořák and Postle as a generalization of list coloring. They used a weak version of DP-coloring to solve a longstanding conjecture by Borodin, stating that every planar graph without cycles of length 4 to 8 is 3-choosable. Liu and Li improved the result by showing that every planar graph without adjacent cycles of length at most 8 is 3-choosable. In this paper, it is showed that every planar graph without $5^{-}$-cycles normally adjacent to $8^{-}$-cycles is 3-choosable. Actually, all these three papers give more stronger results by stating them in the form of weakly DP-3-coloring and color extension.
Introduction
Determining the conditions under which a planar graph is 3-colorable or 3-choosable is a fundamental problem in structural graph theory. While the Four Color Theorem guarantees 4-colorability for all planar graphs, 3-colorability often requires specific structural constraints, typically forbidding short cycles. Grötzsch's Theorem, for instance, establishes that triangle-free planar graphs are 3-colorable. This research explores the boundaries of 3-choosability—a more restrictive property where each vertex has a list of three available colors—by focusing on the proximity of short cycles rather than their mere existence.
Structural Constraints and the Class $\mathcal{G}$
The authors define a specific class of planar graphs, denoted as $\mathcal{G}$, characterized by the avoidance of certain "normally adjacent" cycle configurations. Two cycles are considered normally adjacent if they share exactly one edge. The class $\mathcal{G}$ forbids:
- Triangles ($3$-cycles) normally adjacent to cycles of length $\le 8$.
- $4$-cycles normally adjacent to cycles of length $\le 6$.
- Normally adjacent $5$-cycles.
By refining these adjacency constraints, the paper provides a more nuanced requirement for 3-choosability than previous theorems that forbade cycles of certain lengths entirely.
Methodology
The proof utilizes two primary theoretical frameworks:
- DP-coloring (Correspondence Coloring): A generalization of list coloring that reduces the problem to finding an independent set in a larger cover graph. The authors establish a "weak" version of DP-3-coloring, which is a stronger result than standard 3-choosability.
- The Discharging Method: A standard technique in planar graph theory. Initial charges are assigned to vertices and faces based on Euler’s formula ($V - E + F = 2$). Discharging rules are then applied to redistribute these charges. The proof shows that a minimal counterexample would lead to a contradiction of Euler's formula, thereby proving its non-existence.
Key Insights: Abnormal Cycles
A critical component of the proof involves identifying "abnormal" cycles of length 11 and 12. These configurations pose specific challenges when attempting to extend a partial coloring to the entire graph.
The distinction between "normal" and "abnormal" cycles allows for a more precise definition of the conditions under which color extension is possible. Furthermore, the paper demonstrates that graphs in $\mathcal{G}$ admit an IF-coloring, meaning their vertex set can be partitioned into an independent set and a set that induces a forest.
Key Results
The main contributions of this work are summarized in the following theorems:
- Theorem 1.7: Every graph in the class $\mathcal{G}$ is 3-choosable. This result generalizes and improves upon previous work by Dvořák and Postle (2018) and Liu and Li (2019).
- Theorem 1.12: The vertex set of any graph in $\mathcal{G}$ can be partitioned into an independent set and a forest.
Specific corollaries include the 3-choosability of planar graphs without 4-, 6-, and 8-cycles, as well as those without 4-, 5-, 7-, and 8-cycles.
Conclusion and Future Work
This paper advances the understanding of how cycle adjacency affects the coloring properties of planar graphs. While it provides significant improvements, the authors note that the field is evolving rapidly. Future research may further relax these cycle constraints or extend the results to full DP-3-colorability without the current technical restrictions on closed walks of length 3.
Summary updated