























We call a multigraph $(k,d)$-edge colourable if its edge set can be partitioned into $k$ subgraphs of maximum degree at most $d$ and denote as $χ'_{d}(G)$ the minimum $k$ such that $G$ is $(k,d)$-edge colourable. We prove that for every integer $d$, every multigraph $G$ with maximum degree $Δ$ is $(\lceil \fracΔ{d} \rceil, d)$-edge colourable if $d$ is even and $(\lceil \frac{3Δ- 1}{3d - 1} \rceil, d)$-edge colourable if $d$ is odd and these bounds are tight. We also prove that for every simple graph $G$, $χ'_{d}(G) \in \{ \lceil \fracΔ{d} \rceil, \lceil \frac{Δ+1}{d} \rceil \}$ and characterize the values of $d$ and $Δ$ for which it is NP-complete to compute $χ'_d(G)$. These results generalize several classic results on the chromatic index of a graph by Shannon, Vizing, Holyer, Leven and Galil.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。