Maximum $k$-colourable induced subgraphs in $(P_5+rK_1)$-free graphs

Cicely Henderson; Evelyne Smith-Roberge; Sophie Spirkl; Rebecca Whitman

paper

Maximum $k$ -colourable induced subgraphs in $(P_{5} + r K_{1})$ -free graphs

arXiv:2410.08077

Abstract

We show that for any nonnegative integer $r$ , the Weighted Maximum List- $k$ -Colourable Induced Subgraph problem can be solved in polynomial time for input graphs that do not contain $(P_{5} + r K_{1})$ as an induced subgraph, and give an explicit algorithm demonstrating this. This answers a question of Agrawal et al.\ (2024).

Maximum k-colourable induced subgraphs in (P5​+rK1​)-free graphs

Abstract

Maximum $k$ -colourable induced subgraphs in $(P_{5} + r K_{1})$ -free graphs