Source-linked AI summary
Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8
Zdenek Dvorak, Luke Postle
TL;DR
The paper addresses the difficulty of applying reducible-configuration arguments to list coloring, where vertex identification is generally unavailable. It introduces correspondence coloring to enable such reductions and proves that every planar graph without cycles of lengths 4 to 8 is 3-choosable.
Problem
List-coloring arguments based on reducible configurations cannot generally identify vertices because vertices may have different lists.
Method
The paper generalizes list coloring to correspondence coloring, enabling reductions using vertex identification and minimal-counterexample arguments.
Results
Every planar graph without cycles of lengths 4 to 8 is 3-choosable.
Takeaways & Limitations
Correspondence coloring serves as a tool for studying list colorings and supports the paper’s planar 3-choosability result.
Takeaways & Limitations
The stronger correspondence-coloring claim is not established because the main reduction requires consistency on closed walks of length 3.
Abstract
from arXiv · showhide
We introduce a new variant of graph coloring called correspondence coloring which generalizes list coloring and allows for reductions previously only possible for ordinary coloring. Using this tool, we prove that excluding cycles of lengths 4 to 8 is sufficient to guarantee 3-choosability of a planar graph, thus answering a question of Borodin.
1 Introduction
The paper introduces correspondence coloring to recover vertex-identification reductions unavailable in list coloring, then applies it to planar graphs excluding cycles of lengths 4 to 8. This proves such graphs are 3-choosable, resolving Borodin’s longstanding question.
- Motivation and method: Reducible configurations repeatedly replace a graph by a smaller one whose colorings extend back to the original graph.The new framework enables vertex-identification reductions that generally fail for list assignments with different vertex lists.
- Main result: Theorem 1 proves every planar graph without cycles of lengths 4 to 8 is 3-choosable.This answers a question that had remained open for more than 15 years.
- Correspondence coloring: Correspondence coloring generalizes list coloring by prescribing partial matchings between colors on adjacent vertices.An ordinary list-coloring constraint is recovered when each matching pairs common colors.
- Main result: Theorem 6 establishes C-colorability for every 3-correspondence assignment consistent on every closed walk of length 3.Lemma 5 connects this correspondence-coloring statement to 3-choosability.
- Further applications: The correspondence framework has broader applications, including probabilistic arguments and characterizations of sparse correspondence-critical graphs.These applications use new correspondences or the inductive power of correspondence assignments.
2 Straightness of correspondence assignments
Straightness can be imposed on a subgraph by renaming colors when its cycles are consistent and full, simplifying correspondence assignments for subsequent arguments. The fullness condition is essential and cannot generally be removed.
- A subgraph H is eligible for straightening when every cycle in H is consistent and all cycle edges are full.Under these conditions, an equivalent correspondence assignment exists in which every edge of H is straight.
- Renaming colors along a spanning tree makes all tree edges straight, while consistency forces each remaining edge of H to become straight.The construction processes vertices in depth-first order; each non-tree edge is handled through its fundamental cycle.
- Forests always satisfy the lemma because they contain no cycles requiring consistency or fullness checks.
- The assumption that every cycle edge is full is necessary: a consistent triangle with a 2-correspondence assignment may have no equivalent all-straight assignment.The paper gives a triangle whose correspondence edges prevent simultaneous straightening despite cycle consistency.
3 The main result
The paper proves that every planar graph without cycles of lengths 4 through 8 is 3-choosable by establishing extension properties for correspondence colorings and eliminating minimal counterexamples.
- The main extension theorem: Theorem 8 guarantees extension of any precoloring of at most 12 vertices under a consistent 3-correspondence assignment.The precolored set is either a single vertex or all vertices incident with a face.
- Minimal counterexamples: A minimal-counterexample argument establishes structural properties including connectivity, 2-connectivity, short-cycle restrictions, and constraints on low-degree vertices and faces.These properties include induced outer-face boundaries and restrictions on short paths between precolored vertices.
- Correspondence constraints: Every edge outside the precolored set has at least two correspondence edges, and every such edge not in a triangle is full.These correspondence constraints are derived by adding matchings while preserving the assumptions and contradicting minimality.
- Correspondence constraints: Triangles containing two non-precolored degree-three vertices have all their edges full, while consistency on triangular walks rules out certain partial matchings.The argument uses color renamings and minimality to strengthen local correspondence structure.
- The tetrad reduction: Every tetrad in a minimal counterexample contains a precolored vertex, enabling a reduction that identifies two external vertices without creating cycles of lengths 4 through 8.The resulting smaller graph remains suitable for Theorem 8, and its coloring extends back to the deleted tetrad.