Edge-colouring and total-colouring chordless graphs

Abstract

A graph $G$ is \emph{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 \ge 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.

References in corpus (4)

• A structure theorem for graphs with no cycle with a unique chord and its consequences
• On graphs with no induced subdivision of $K_4$
• Graphs that do not contain a cycle with a node that has at least two neighbors on it
• Complexity of colouring problems restricted to unichord-free and \{square,unichord\}-free graphs

Cited by in corpus (6)

• Complexity of colouring problems restricted to unichord-free and \{square,unichord\}-free graphs
• The (theta, wheel)-free graphs Part I: only-prism and only-pyramid graphs
• Wheel-free planar graphs
• Total Colourings - A survey
• Acyclic Chromatic Index of Chordless Graphs
• Minimal induced subgraphs of the class of 2-connected non-Hamiltonian wheel-free graphs