Maximum k-colourable induced subgraphs in (P₅+rK₁)-free graphs

2024/10/10 by Cicely Henderson, Evelyne Smith‐Roberge, Henderson, Cicely +5 · 1 citation
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.2410.08077

openalex publication_date 2024/10/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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₅+ rK₁) as an induced subgraph, and give an explicit algorithm demonstrating this. This answers a question of Agrawal et al. (2024).

Cited by

• Maximum list r-colorable induced subgraphs in kP₃-free graphs

Related

• Maximum list r-colorable induced subgraphs in kP₃-free graphs
• Finding large k-colorable induced subgraphs in (bull, chair)-free and (bull,E)-free graphs
• Deciding k-colourability of P₅-free graphs in polynomial time
• Maximum Partial List H-Coloring on P₅-free graphs in polynomial time
• The maximum k-colorable subgraph problem and related problems