论文标题
有关连接的贪婪边缘着色的注释
A note on connected greedy edge colouring
论文作者
论文摘要
在给定的图形$ g $边缘的订购后，贪婪的边缘着色过程将最小的可用颜色分配给每个边缘。如此涉及的最小颜色数量是色度指数$χ'（g）$，最大值是所谓的Grundy色度指数。在这里，我们对边缘订购以连接方式构建图形的有限情况感兴趣。令$χ_c'（g）$为这种订购后涉及的最小颜色数量。我们表明，确定$χ_c'（g）>χ'（g）$是NP-HARD。我们证明$χ'（g）=χ_c'（g）$如果$ g $是两部分，而$χ_c'（g）\ leq 4 $如果$ g $是supubic。
Following a given ordering of the edges of a graph $G$, the greedy edge colouring procedure assigns to each edge the smallest available colour. The minimum number of colours thus involved is the chromatic index $χ'(G)$, and the maximum is the so-called Grundy chromatic index. Here, we are interested in the restricted case where the ordering of the edges builds the graph in a connected fashion. Let $χ_c'(G)$ be the minimum number of colours involved following such an ordering. We show that it is NP-hard to determine whether $χ_c'(G)>χ'(G)$. We prove that $χ'(G)=χ_c'(G)$ if $G$ is bipartite, and that $χ_c'(G)\leq 4$ if $G$ is subcubic.
