By Vizing’s theorem, every graph with maximum degree $\Delta$ can have its edges colored using either $\Delta$ or $\Delta + 1$ colors. For planar graphs, determining exactly when a graph is $\Delta$-edge-colorable—meaning its edges can be perfectly partitioned into $\Delta$ matchings—is a deep structural puzzle.
The foundational anchor for this problem is Tait's Theorem, which establishes that a 3-regular (cubic) planar graph is 3-edge-colorable if and only if it is bridgeless (contains no cut-edges). This simple bridge constraint is famously equivalent to the Four Color Theorem. However, when we move away from strictly 3-regular graphs, or scale up to higher degrees ($\Delta > 3$), the clean characterization breaks down.
To understand why a planar graph admits a perfect edge-coloring, researchers look at the problem through three dual lenses: completions (embedding sparse graphs into regular ones), connectivity parity (ensuring cuts can accommodate color distributions), and topological dualities (viewing colorings as packed structural subgraphs).
The Completion Strategy: Subcubic to Cubic
If a planar graph has a maximum degree of 3 but is not perfectly 3-regular, verifying its 3-edge-colorability is highly non-trivial. One intuitive way to prove a graph is 3-edge-colorable is to "embed" or extend it into a larger, 3-regular planar graph that we already know is colorable (i.e., a bridgeless cubic planar graph). If we can find such a completion, we can color the larger graph and simply inherit the coloring on our original subgraph.
Subcubic Graph (Δ ≤ 3) ──[Augmentation]──> Cubic Bridgeless Planar Graph
│ │
└─────────── Inherits 3-Edge-Coloring <──────────────┘
In Efficient Recognition of Subgraphs of Planar Cubic Bridgeless Graphs, Miriam Goetze et al. provided an efficient $O(n^2)$ algorithm to determine whether a planar graph can be completed into a bridgeless cubic planar graph. This provides a powerful algorithmic pipeline for verifying colorability.
However, the difficulty of this completion strategy depends entirely on the connectivity requirements of the target graph. In a follow-up work, Recognition Complexity of Subgraphs of bf k-Connected Planar Cubic Graphs, the authors mapped out a sharp complexity boundary. They demonstrated that while finding completions into 1-connected or 2-connected cubic planar graphs remains solvable in polynomial time, demanding that the completion be 3-connected causes the problem to become NP-complete. This reveals that the computational ease of verifying colorability via completion is tightly bound to the topological resilience of the target regular graph.
Higher Degrees and Odd Connectivity
For regular planar graphs where $d > 3$, the bridgeless condition is no longer sufficient to guarantee $d$-edge-colorability. Instead, a more subtle structural constraint emerges: odd $d$-edge-connectivity.
To understand why this constraint is necessary, imagine a set containing an odd number of vertices. In a proper $d$-edge-coloring, each color must form a matching. Because the vertex set is odd, no single color matching can pair up all the vertices within the set; every color must have at least one edge leaving the set. Therefore, any cut separating an odd number of vertices must contain at least $d$ edges—one for each color. A graph meeting this requirement is said to be oddly $d$-edge-connected.
Seymour’s conjecture posits that this necessary condition is also sufficient: any $d$-regular planar graph that is oddly $d$-edge-connected must be $d$-edge-colorable. Proving the "if" direction of this statement is notoriously difficult because inductive steps frequently break the strict regularity of the graph.
In Edge-colouring seven-regular planar graphs, Maria Chudnovsky et al. bypassed these hurdles for the $d=7$ case. The authors developed a streamlined inductive proof showing that odd 7-edge-connectivity guarantees 7-edge-colorability. Their approach works by carefully identifying reducible configurations that can be contracted or altered without violating the delicate odd-connectivity constraints of the surrounding graph, providing a blueprint for analyzing higher-degree planar colorings.
Decomposing Colorings into Packed Joins
Why does odd connectivity tightly control edge-colorability? The answer lies in a deep topological duality between edge cuts and subgraph packings.
Instead of assigning colors to individual edges one by one, we can think of a $d$-edge-coloring as decomposing a graph into $d$ edge-disjoint subgraphs with specific parity properties, known as $T$-joins. Given a set of target vertices $T$, a $T$-join is a subgraph where the odd-degree vertices match $T$ exactly. In the dual plane graph, finding edge-disjoint $T$-joins corresponds directly to avoiding bottlenecks caused by small $T$-cuts (cuts that intersect $T$ an odd number of times).
Global Colorability <===> Packing Edge-Disjoint Subgraphs (T-joins)
▲
│ (Planar Duality)
▼
Avoiding Bottlenecks (Small T-cuts)
This perspective allowed Zdenek Dvorák 0001 et al. to settle a long-standing conjecture for the $d=6$ case. In Packing six T-joins in plane graphs, the authors proved that if all $T$-cuts in a planar graph share the same parity and have a minimum size of six, the graph must contain six edge-disjoint $T$-joins.
For a 6-regular plane multigraph, this theorem guarantees that the graph can be perfectly decomposed into six 1-factors, which is equivalent to a 6-edge-coloring. This result demonstrates that edge-colorability is not merely a local combinatorial constraint, but a global property guaranteed by the absence of tight structural bottlenecks.
The Limits of Verification
The deep connection between local packing constraints and global colorability properties is a recurring theme across structural graph theory. For example, Pattara Sukprasert et al. explore a parallel tension in Multi-transversals for Triangles and the Tuza's Conjecture, analyzing the dual relationship between packing edge-disjoint triangles and finding minimum edge coverings to eliminate them.
When we lose the rigid structure of a fixed planar embedding, verifying these properties becomes significantly harder. In Coloring Drawings of Graphs, Christoph Hertrich et al. extended coloring problems to non-planar graphs by looking at their drawings. They introduced "universal cell 3-colorability"—a property where the faces of every possible planar drawing of a graph can be 3-colored.
This highlights a fundamental computational barrier: while a standard graph coloring can be easily verified with a "short certificate" (the coloring itself), proving that a graph remains colorable across all possible topological drawings lacks an efficient verification method. The authors note that it remains an open question whether recognizing universally colorable graphs even sits within the complexity class NP.
Ultimately, the research shows that planar edge-colorability works because planarity imposes strict dualities. Whether by completing subcubic graphs, tracking odd cuts, or packing $T$-joins, global colorability is always governed by a predictable balance between local density and global connectivity.
Key Foundational Work
Packing six T-joins in plane graphs (2016) — contributed 5 concept elements to this direction.
Edge-colouring seven-regular planar graphs (2015) — contributed 4 concept elements to this direction.