Parameterizing role coloring on forests

DOI10.1007/978-3-030-67731-2_22MaRDI QIDQ831825zbMATH OpenOpenAlexFDO

Authors Sukanya Pandey, Venkatesh Raman, Vibha Sahlot

Publication date 24 March 2022

Full work available at URL https://doi.org/10.1007/978-3-030-67731-2_22

zbMATH Keywords

treesforestsFPTrole coloring

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Coloring of graphs and hypergraphs (05C15) Parameterized complexity, tractability and kernelization (68Q27)

Recommendations

• Role coloring bipartite graphs
• On the complexity of role colouring planar graphs, trees and cographs
• Fixed-parameter tractability of \((n-k)\) list coloring
• Role colouring graphs in hereditary classes
• On the parameterized complexity of coloring graphs in the absence of a linear forest

Cites work

• scientific article; zbMATH DE number 1261820 (Why is no real title available?)
• A complete complexity classification of the role assignment problem
• Color-coding
• Computing role assignments of chordal graphs
• Computing role assignments of proper interval graphs in polynomial time
• Computing role assignments of split graphs
• Constant Time Generation of Free Trees
• Fixed-parameter tractability of \((n-k)\) list coloring
• Graph-Theoretic Concepts in Computer Science
• How hard is it to determine if a graph has a 2-role assignment?
• Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree
• On the complexity of role colouring planar graphs, trees and cographs
• Parameterized pre-coloring extension and list coloring problems
• Regular equivalence: General theory
• Role coloring bipartite graphs
• Role colouring a graph
• Some simplified NP-complete graph problems
• The number of trees

Cited in

(5)

• On the complexity of role colouring planar graphs, trees and cographs
• An algorithmic framework for locally constrained homomorphisms
• Making Role Assignment Feasible: A Polynomial-Time Algorithm for Computing Ecological Colorings
• Role colouring graphs in hereditary classes
• An algorithmic framework for locally constrained homomorphisms

This page was built for publication: Parameterizing role coloring on forests

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