Edge-colouring and total-colouring chordless graphs
classification
💻 cs.DM
math.CO
keywords
chordlesschromaticdeltagraphgraphsindexnumbertotal
read the original 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\geq 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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.