Parameterized algorithms for Max Colorable Induced Subgraph problem on perfect graphs

DOI10.1007/s00453-018-0431-8zbMath1414.05128MaRDI QIDQ1755775

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

Publication date: 11 January 2019

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-018-0431-8

zbMATH Keywords

perfect graphs; co-chordal graphs; maximum induced subgraphs; polynomial kernel lower bounds; randomized FPT algorithms

Mathematics Subject Classification ID

05C15: Coloring of graphs and hypergraphs

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

68W20: Randomized algorithms

05C17: Perfect graphs