PreprintarXiv licencearXiv
A proof of Wang's planar D-coloring conjecture
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 K4 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 Δ≥ 6. Hu, Kong and Wang proved the cases Δ≤ 5 and Δ≥ 33. We prove the sharp bound 2Δ−1 for every Δ≥ 6, settling the remaining cases. The proof uses discharging; the case Δ=6 is computer-assisted.
Related
- The Borowiecki-Broere Generalized Total Coloring Conjecture for Planar Graphs
- Proof of the planar Khavinson-Shapiro conjecture
- Proof of the mad conjecture and its coloring applications
- Rayleigh's conjecture for vibrating plates: simpler planar proof and nonlinear extensions
- Bounds for B-coloring planar and outerplanar graphs
BibTeX
@misc{verma2026proof,
title = {{A proof of Wang's planar D-coloring conjecture}},
author = {Harshit Verma},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.33322},
eprint = {2610.33322},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.33322},
}
RIS
TY - UNPB
TI - A proof of Wang's planar D-coloring conjecture
AU - Harshit Verma
PY - 2026
DA - 2026/10/23
PB - arXiv
DO - 10.48550/arxiv.2610.33322
UR - https://arxiv.org/abs/2610.33322
AB - 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 Δ≥ 6. Hu, Kong and Wang proved the cases Δ≤ 5 and Δ≥ 33. We prove the sharp bound 2Δ−1 for every Δ≥ 6, settling the remaining cases. The proof uses discharging; the case Δ=6 is computer-assisted.
ER -