pith. sign in

arxiv: 1309.2749 · v1 · pith:IJ6UJRCNnew · submitted 2013-09-11 · 💻 cs.DM · math.CO

Complexity of colouring problems restricted to unichord-free and \{square,unichord\}-free graphs

classification 💻 cs.DM math.CO
keywords unichord-freegraphemphgraphsunichordclasscolouringcycle
0
0 comments X
read the original abstract

A \emph{unichord} in a graph is an edge that is the unique chord of a cycle. A \emph{square} is an induced cycle on four vertices. A graph is \emph{unichord-free} if none of its edges is a unichord. We give a slight restatement of a known structure theorem for unichord-free graphs and use it to show that, with the only exception of the complete graph $K_4$, every square-free, unichord-free graph of maximum degree~3 can be total-coloured with four colours. Our proof can be turned into a polynomial time algorithm that actually outputs the colouring. This settles the class of square-free, unichord-free graphs as a class for which edge-colouring is NP-complete but total-colouring is polynomial.

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.