Role colouring graphs in hereditary classes

DOI10.1016/J.TCS.2021.05.010MaRDI QIDQ6298325arXivFDO

Authors Christopher Purcell, Puck Rombach

Publication date 27 February 2018

Published in arXiv

Full work available at URL https://doi.org/10.1016/J.TCS.2021.05.010

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Structural characterization of families of graphs (05C75) Analysis of algorithms and problem complexity (68Q25)

arXiv classification

cs.CCmath.CO

Abstract: We study the computational complexity of computing role colourings of graphs in hereditary classes. We are interested in describing the family of hereditary classes on which a role colouring with k colours can be computed in polynomial time. In particular, we wish to describe the boundary between the "hard" and "easy" classes. The notion of a boundary class has been introduced by Alekseev in order to study such boundaries. Our main results are a boundary class for the k-role colouring problem and the related k-coupon colouring problem which has recently received a lot of attention in the literature. The latter result makes use of a technique for generating regular graphs of arbitrary girth which may be of independent interest.

This page was built for publication: Role colouring graphs in hereditary classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6298325)