On the complexity of role colouring planar graphs, trees and cographs

DOI10.1016/J.JDA.2015.08.001MaRDI QIDQ891815zbMATH OpenOpenAlexFDO

Authors Christopher Purcell, Puck Rombach

Publication date 17 November 2015

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

cographcomplexitylocally surjective homomorphismplanar graphregular equivalencerole colouringtree

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Abstract: We prove several results about the complexity of the role colouring problem. A role colouring of a graph $G$ is an assignment of colours to the vertices of $G$ such that two vertices of the same colour have identical sets of colours in their neighbourhoods. We show that the problem of finding a role colouring with $1<k<n$ colours is NP-hard for planar graphs. We show that restricting the problem to trees yields a polynomially solvable case, as long as $k$ is either constant or has a constant difference with $n$, the number of vertices in the tree. Finally, we prove that cographs are always $k$-role-colourable for $1<kleqn$ and construct such a colouring in polynomial time.

Recommendations

• Parameterizing role coloring on forests
• Role coloring bipartite graphs
• Computing Role Assignments of Chordal Graphs
• Role colouring graphs in hereditary classes
• The complexity of harmonious colouring for trees

Cites work

• 2-role assignments on triangulated graphs.
• A complete complexity classification of the role assignment problem
• A simplified NP-complete satisfiability problem
• Comparing Universal Covers in Polynomial Time
• Computing role assignments of chordal graphs
• How hard is it to determine if a graph has a 2-role assignment?
• scientific article; zbMATH DE number 1003286 (Why is no real title available?)
• scientific article; zbMATH DE number 1270594 (Why is no real title available?)
• scientific article; zbMATH DE number 1456953 (Why is no real title available?)
• On a property of the class of n-colorable graphs
• Planar Formulae and Their Uses
• Regular equivalence: General theory
• Role colouring a graph
• The complexity of theorem-proving procedures

Cited in

(10)

• Role colouring a graph
• Role colouring graphs in hereditary classes
• Role coloring bipartite graphs
• Edge homogeneous colorings
• Some properties of intersection graph of a module with an application of the graph of \(\mathbb{Z}_n\)
• Making Role Assignment Feasible: A Polynomial-Time Algorithm for Computing Ecological Colorings
• An algorithmic framework for locally constrained homomorphisms
• An algorithmic framework for locally constrained homomorphisms
• Computing a 3-role assignment is polynomial-time solvable on complementary prisms
• Parameterizing role coloring on forests

This page was built for publication: On the complexity of role colouring planar graphs, trees and cographs

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