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

DOI10.1016/J.JDA.2015.08.001zbMATH Open1343.68121arXiv1408.5412OpenAlexW2963336224MaRDI QIDQ891815FDOQ891815

Christopher Purcell, Puck Rombach

Publication date: 17 November 2015

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

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.

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

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

zbMATH Keywords

treeregular equivalencecomplexityplanar graphcographlocally surjective homomorphismrole colouring

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (8)

• Parameterizing role coloring on forests
• An algorithmic framework for locally constrained homomorphisms
• Role coloring bipartite graphs
• Making Role Assignment Feasible: A Polynomial-Time Algorithm for Computing Ecological Colorings
• Role colouring graphs in hereditary classes
• Some properties of intersection graph of a module with an application of the graph of ℤ_n
• An algorithmic framework for locally constrained homomorphisms
• Edge homogeneous colorings

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)