Proof confirms color patterns for planar graphs with limited edges
A proof of Wang's planar D-coloring conjecture
Discrete Mathematics
Summary
This paper solves a longstanding math puzzle about coloring the edges of certain flat graphs so that specific small groups of edges each show different colors. The authors confirmed precise rules for how many colors are needed based on the graph’s maximum number of edges meeting at a point. Their work completes cases left unsolved by earlier researchers, using a method called discharging and computer checks for one case. This advances understanding of complex coloring problems in graph theory.
What this means in practice
- •For graph algorithm designers: Use the confirmed color bounds to develop efficient algorithms for edge coloring planar graphs with degree constraints.
- •For network layout engineers: Design communication or wiring networks planar with guaranteed distinct signal paths avoiding certain edge overlaps.
A theory result. No direct application yet.
Authors
Harshit Verma
Abstract
We prove Wang's planar D-coloring conjecture. A D-coloring of a graph is a proper edge coloring in which every subgraph isomorphic to $K_4$ minus an edge is rainbow. Wang conjectured that every planar graph of maximum degree $Δ$ has a D-coloring with 9 colors if $Δ=4$, 10 colors if $Δ=5$, and $2Δ-1$ colors if $Δ\ge 6$. Hu, Kong and Wang proved the cases $Δ\le 5$ and $Δ\ge 33$. We prove the sharp bound $2Δ-1$ for every $Δ\ge 6$, settling the remaining cases. The proof uses discharging; the case $Δ=6$ is computer-assisted.