D-coloring of planar graphs

Xiaoxue Hu; Jiangxu Kong; Yiqiao Wang; Yiqiang Wang

combinatorics

D-coloring of planar graphs

arXiv:2607.14837

summary

The paper investigates D‑colorings—proper edge‑colorings where every K4‑e subgraph is rainbow—of planar graphs and establishes tight upper bounds on the D‑chromatic index for graphs with maximum degree up to 4, exactly 5, and at least 33, confirming Wang’s conjecture in those ranges.

Abstract

A proper edge-coloring of a graph $G$ is a D-coloring if every subgraph isomorphic to $K_{4} - e$ is rainbow. The minimum number of colors in such a coloring is the D-chromatic index $I ¨ _{D}^{'} (G)$ . Wang conjectured that every planar graph of maximum degree $I^ \geq 4$ satisfies $I ¨ _{D}^{'} (G) \leq 9$ for $I^ = 4$ , $I ¨ _{D}^{'} (G) \leq 10$ for $I^ = 5$ , and $I ¨ _{D}^{'} (G) \leq 2 I^ - 1$ for $I^ \geq 6$ . We prove that every planar graph $G$ satisfies \[ Ï_D'(G) \leq \begin{cases} 9, & Î(G) \leq 4, \\ 10, & Î(G) = 5, \\ 2Î(G) - 1, & Î(G) \geq 33. \end{cases} \] Each bound is best possible in its stated range. Consequently, Wang's conjecture remains open only for $6 \leq I^ \leq 32$ .

Topics & keywords

#planar graphs #edge coloring #graph theory #chromatic index #D-coloringD-coloringrainbow subgraphK4-emaximum degreeplanar graphchromatic index