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

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 $(P_{5} + r K_{1})$ -free graphs

文献摘要

讨论

讲解博客

AI智能校验

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

文献摘要

讨论

讲解博客

AI智能校验

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

文献摘要

讨论

|讲解博客

|AI智能校验

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

文献摘要

讨论

|讲解博客

|AI智能校验

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

讲解博客

AI智能校验

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

讲解博客

AI智能校验