Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4647688 | Discrete Mathematics | 2013 | 6 Pages |
Abstract
A graph GG is chordless if no cycle in GG 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Δ≥3 has chromatic index ΔΔ and total chromatic number Δ+1Δ+1. The proofs are algorithmic in the sense that we actually output an optimal colouring of a graph instance in polynomial time.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Raphael C.S. Machado, Celina M.H. de Figueiredo, Nicolas Trotignon,