Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
419096 | Discrete Applied Mathematics | 2014 | 9 Pages |
Abstract
A unichord in a graph is an edge that is the unique chord of a cycle. A square is an induced cycle on four vertices. A graph is 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 K4K4, 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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Raphael C.S. Machado, Celina M.H. de Figueiredo, Nicolas Trotignon,