Edge-colouring and total-colouring chordless graphs
Edge-colouring and total-colouring chordless graphs
复制标题
DOI：
10.1016/j.disc.2013.03.020
复制
发表时间：
2013-07
期刊：
影响因子：
--
通讯作者：
R. Machado;C. M. Figueiredo;Nicolas Trotignon
中科院分区：
文献类型：
--
作者：
R. Machado;C. M. Figueiredo;Nicolas Trotignon
如果图G中没有圈有弦，则图G是无弦的。在本文中，我们研究了无弦图的色指数和全色数。我们描述了无弦图的一个已知分解结果，并利用它证明了每个最大度Δ≥为3的无弦图都有色指数Δ和全色数Δ+1。证明是算法的，因为我们实际上在多项式时间内输出了一个图实例的最优着色。
A graph G is chordless if no cycle in G has a chord. In the present work we investigate the chromatic index and total chromatic number of chordless graphs. We describe a known decomposition result for chordless graphs and use it to establish that every chordless graph of maximum degree Δ≥3 has chromatic index Δ and total chromatic number Δ+1. The proofs are algorithmic in the sense that we actually output an optimal colouring of a graph instance in polynomial time.