An Efficient Algorithm for Colouring the Edges of a Graph With Δ + 1 Colours
An Efficient Algorithm for Colouring the Edges of a Graph With Δ + 1 Colours
复制标题
一种用 Δ + 1 种颜色为图的边缘着色的高效算法
DOI：
--
复制
发表时间：
1982
期刊：
影响因子：
--
通讯作者：
E. Arjomandi
中科院分区：
文献类型：
--
作者：
E. Arjomandi
边着色问题一直受到数学家和计算机科学家的广泛关注。简单图G的边可以用Δ或Δ + 1色着色，其中Δ是G的最大度。Holyer最近证明了A边着色是NP完全的。本文给出了一般图的边着色算法，它至多使用Δ + 1种颜色。
AbstractThe edge colouring problem has received considerable attention from mathematicians andcomputer scientists. The edges of a simple graph G can be coloured with Δ or Δ + 1 colours, where Δ is the maximum degree in G. Holyer has recently shown that A-edgecolourability is NP-complete. In this paper we present a edge colouring algorithm for general graphs which uses at most Δ + 1 colours.