Maximum $k$-colourable induced subgraphs in $(P_5+rK_1)$-free graphs
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866915616941670400 |
|---|---|
| author | Henderson, Cicely Smith-Roberge, Evelyne Spirkl, Sophie Whitman, Rebecca |
| author_facet | Henderson, Cicely Smith-Roberge, Evelyne Spirkl, Sophie Whitman, Rebecca |
| contents | 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+ rK_1)$ as an induced subgraph, and give an explicit algorithm demonstrating this. This answers a question of Agrawal et al.\ (2024). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_08077 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Maximum $k$-colourable induced subgraphs in $(P_5+rK_1)$-free graphs Henderson, Cicely Smith-Roberge, Evelyne Spirkl, Sophie Whitman, Rebecca Combinatorics 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+ rK_1)$ as an induced subgraph, and give an explicit algorithm demonstrating this. This answers a question of Agrawal et al.\ (2024). |
| title | Maximum $k$-colourable induced subgraphs in $(P_5+rK_1)$-free graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2410.08077 |