Computing a 3-role assignment is polynomial-time solvable on complementary prisms

DOI10.1142/S012905412550011XMaRDI QIDQ6854533zbMATH OpenFDO

Authors Diane Castonguay, Elisângela S. Dias, Fernanda Neiva Mesquita, Julliano Rosa Nascimento

Publication date 24 February 2026

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/S012905412550011X

zbMATH Keywords

complementary prismpolynomial timerole assignment

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Cites work

• A complete complexity classification of the role assignment problem
• Complementary prisms with 2-assignment of roles
• Computing role assignments of Cartesian product of graphs
• Computing role assignments of chordal graphs
• Computing role assignments of split graphs
• Computing some role assignments of Cartesian product of graphs
• How hard is it to determine if a graph has a 2-role assignment?
• Introduction to algorithms.
• Local computations in graphs: the case of cellular edge local computations
• On the complexity of role colouring planar graphs, trees and cographs
• Role colouring a graph
• Study on (r+1)-role assignments of complementary prisms, with r 3
• The complementary product of two graphs
• The Complexity of Near-Optimal Graph Coloring

This page was built for publication: Computing a 3-role assignment is polynomial-time solvable on complementary prisms

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