pith. sign in

arxiv: 1309.1842 · v1 · pith:JZZMT2KEnew · submitted 2013-09-07 · 💻 cs.DM · math.CO

Edge-colouring and total-colouring chordless graphs

classification 💻 cs.DM math.CO
keywords chordlesschromaticdeltagraphgraphsindexnumbertotal
0
0 comments X
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.