TOPICS
Search

D-Coloring


A D-coloring of a simple graph is a proper edge coloring in which every subgraph isomorphic to the diamond graph is a rainbow subgraph. Thus the five edges of each such diamond receive five different colors (Wang 2026).

Verma (2026) proved that every planar graph of maximum vertex degree Delta>=6 has a D-coloring using at most 2Delta-1 colors, completing Wang's conjecture. The case Delta=6 uses computer-assisted verification of reducible configurations.

A B-coloring, which requires every cycle graph C_4 to be rainbow in addition to properness, is a stronger condition. The outer C_4 of a diamond graph uses four distinct colors, and its remaining graph edge must receive a fifth. Conversely, a two-color edge coloring of C_4 is a D-coloring but not a B-coloring.


See also

Diamond Graph, Edge Coloring, Rainbow Subgraph

Explore with Wolfram|Alpha

References

Verma, H. "A Proof of Wang's Planar D-Coloring Conjecture." 23 Oct 2026. https://arxiv.org/abs/2610.33322.Wang, R. "Proper Edge Coloring with Rainbow Diamonds." 5 Jun 2026. https://arxiv.org/abs/2606.06831.

Cite this as:

Weisstein, Eric W. "D-Coloring." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/D-Coloring.html

Subject classifications