Finding large $k$-colorable induced subgraphs in (bull, chair)-free and (bull,E)-free graphs
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909577945022464 |
|---|---|
| author | Hodur, Nadzieja Pilśniak, Monika Prorok, Magdalena Rzążewski, Paweł |
| author_facet | Hodur, Nadzieja Pilśniak, Monika Prorok, Magdalena Rzążewski, Paweł |
| contents | 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^{\mathcal{O}(kω)}$ if the input graph excludes the bull and the chair as an induced subgraph,
* $n^{\mathcal{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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_04984 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Finding large $k$-colorable induced subgraphs in (bull, chair)-free and (bull,E)-free graphs Hodur, Nadzieja Pilśniak, Monika Prorok, Magdalena Rzążewski, Paweł Computational Complexity Combinatorics 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^{\mathcal{O}(kω)}$ if the input graph excludes the bull and the chair as an induced subgraph, * $n^{\mathcal{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. |
| title | Finding large $k$-colorable induced subgraphs in (bull, chair)-free and (bull,E)-free graphs |
| topic | Computational Complexity Combinatorics |
| url | https://arxiv.org/abs/2504.04984 |