Article ID Journal Published Year Pages File Type
4647688 Discrete Mathematics 2013 6 Pages PDF
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
, , ,