Parameterized Algorithms for Max Colorable Induced Subgraph Problem on Perfect Graphs

DOI10.1007/978-3-642-45043-3_32zbMath1417.05082OpenAlexW2152355908MaRDI QIDQ2864316

Ashutosh Rai, Fahad Panolan, Saket Saurabh, Neeldhara Misra, Venkatesh Raman

Publication date: 6 December 2013

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-45043-3_32

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Perfect graphs (05C17)

Related Items (5)

Linear-Time Generation of Random Chordal Graphs ⋮ Reconfiguration of colorable sets in classes of perfect graphs ⋮ Parameterized algorithms for non-separating trees and branchings in digraphs ⋮ Two generalizations of proper coloring: hardness and approximability ⋮ Inductive \(k\)-independent graphs and \(c\)-colorable subgraphs in scheduling: a review

This page was built for publication: Parameterized Algorithms for Max Colorable Induced Subgraph Problem on Perfect Graphs