论文标题
vize和香农的定理，用于有缺陷的边缘着色
Vizing's and Shannon's Theorems for defective edge colouring
论文作者
论文摘要
如果将其边缘集可以分配到最多$ d $的最高学位的$ K $子图中，我们将其称为Multigraph $（k，d）$ - edge-edge-Edge Colourourable，并表示为$χ'__ {d}（g）$最小$ k $，以至于$ g $是$ g $ is $ is $ is（k，d）$ - edge-edge-edge-geed-geed-gedureable。我们证明，对于每一个整数$ d $，每个多数$ g $带有最高度$δ$为$（\ lceil \fracδ{d} \ rceil，d）$ - $ - ed $ ded $，如果$ d $均匀而$ d $ ever and $ de $（\ lceil \ lceil \ frac \ frac {3Δ-1}} {3D-1} {3D-1} $ dege $ dege $ dise $ dise off thus ys d $ dthe $ - 紧的。我们还证明，对于每个简单的图形$ g $，$χ'_{d}（g）\ in \ in \ {\ lceil \fracΔ{d} \ rceil，\ lceil \ lceil \ frac {Δ+1} {δ+1} {d} {d} {d} {d} {d} {d} {d} $χ'_d（g）$。这些结果概括了Shannon，Vible，Holyer，Leven和Galil的图表上的几个经典结果。
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.
