Edge-colouring and total-colouring chordless graphs

被引：17

作者：

Machado, Raphael C. S. ^{[1
]}

de Figueiredo, Celina M. H. ^{[2
]}

Trotignon, Nicolas ^{[3
]}

机构：

[1] Inmetro, Rio De Janeiro, Brazil

[2] Univ Fed Rio de Janeiro, COPPE, BR-21941 Rio De Janeiro, Brazil

[3] ENS Lyon, CNRS, LIP, Lyon, France

来源：

DISCRETE MATHEMATICS | 2013年 / 313卷 / 14期

关键词：

Chordless graph; Graph decomposition; Edge-colouring; Total-colouring; TOTAL-CHROMATIC NUMBER; NP-COMPLETENESS; PLANAR GRAPHS; INDEX; CYCLE;

D O I：

10.1016/j.disc.2013.03.020

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

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 Delta >= 3 has chromatic index Delta and total chromatic number Delta + 1. The proofs are algorithmic in the sense that we actually output an optimal colouring of a graph instance in polynomial time. (C) 2013 Elsevier B.V. All rights reserved.

引用

页码：1547 / 1552

页数：6

共 38 条

[1] GRAPHS THAT DO NOT CONTAIN A CYCLE WITH A NODE THAT HAS AT LEAST TWO NEIGHBORS ON IT [J].