Finding large k-colorable induced subgraphs in (bull, chair)-free and (bull,E)-free graphs

2025/04/07 by Nadzieja Hodur, Monika Pilśniak, Hodur, Nadzieja +5 · 2 citations
Computer Science · Decision Sciences · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory #Scheduling and Timetabling Solutions

paper · pdf · doi:10.48550/arxiv.2504.04984

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

Abstract

We study the Max Partial k-Coloring problem, where we are given a vertex-weighted graph, and we ask for a maximum-weight induced subgraph that admits a proper k-coloring. For k=1 this problem coincides with Maximum Weight Independent Set, and for k=2 the problem is equivalent (by complementation) to Minimum Odd Cycle Transversal. Furthermore, it generalizes k-Coloring. We show that Max Partial k-Coloring on n-vertex instances with clique number ω can be solved in time * n^O(kω) if the input graph excludes the bull and the chair as an induced subgraph, * n^{O(kωlog n)} if the input graph excludes the bull and E as an induced subgraph. This implies that k-Coloring can be solved in polynomial time in the former class, and in quasipolynomial-time in the latter one.

Cited by

• Hitting all longest paths in H-free graphs and H-graphs
• On k-colorability of (bull, H)-free graphs

Related

• Maximum list r-colorable induced subgraphs in kP₃-free graphs
• Maximum k-colourable induced subgraphs in (P₅+rK₁)-free graphs
• Finding large H-colorable subgraphs in hereditary graph classes
• Maximum Partial List H-Coloring on P₅-free graphs in polynomial time
• The maximum k-colorable subgraph problem and related problems