Role colouring graphs in hereditary classes

DOI10.1016/j.tcs.2021.05.010OpenAlexW3162718730MaRDI QIDQ2034782

Christopher Purcell, Puck Rombach

Publication date: 23 June 2021

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1802.10180

zbMATH Keywords

computational complexityrole colouringhereditary classesboundary classescoupon colouring

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (1)

An algorithmic framework for locally constrained homomorphisms

Cites Work

• Unnamed Item
• Unnamed Item
• Computing role assignments of split graphs
• Coupon coloring of some special graphs
• Boundary properties of graphs for algorithmic graph problems
• An O(\(n\)) time algorithm for maximum matching on cographs
• Graph minors. XX: Wagner's conjecture
• Computing role assignments of chordal graphs
• A complete complexity classification of the role assignment problem
• On the complexity of role colouring planar graphs, trees and cographs
• On easy and hard hereditary classes of graphs with respect to the independent set problem
• On the connectivity of certain graphs of high girth.
• Coupon coloring of cographs
• Explicit construction of graphs with an arbitrary large girth and of large size
• Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree
• On coupon colorings of graphs
• Boundary properties of the satisfiability problems
• Regular equivalence: General theory
• The complexity of satisfiability problems
• NP-completeness results for partitioning a graph into total dominating sets

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