2018/02/27 by Purcell, Christopher, Rombach, Puck
#05C15 #05C75 #05C85 #68R10 #68W40 #Combinatorics (math.CO) #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.1802.10180
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.