标题： 最大$r$-可着色诱导子图在$kP_3$-自由图中的数量 显示英文标题

标题： Maximum list $r$-colorable induced subgraphs in $kP_3$-free graphs

摘要： 我们证明，对于每个固定的正整数$r$和$k$，\textsc{最大权重列表$r$-可着色诱导子图}在$kP_3$-自由图上存在一个多项式时间算法。这个问题是\textsc{最大权重独立集}、\textsc{奇环 穿越}和\textsc{列表$r$-着色}等问题的共同推广。我们的结果有若干推论。 首先，这意味着，对于每一个固定的$r \geq 5$，假设$\mathsf{P}\neq \mathsf{NP}$，如果并且仅当$H$是某个$k \geq 1$下的$H$-free 图中$kP_3$或$P_5+kP_1$的导出子图时，\textsc{最大权重列表$r$-可着色诱导子图}在多项式时间内可解。 其次，它在关于$H$-自由图上的\textsc{奇圈 穿刺}的复杂性二分法方面取得了显著进展，使得能够回答Agrawal、Lima、Lokshtanov、Rz{\k{a}}żewski、Saurabh和Sharma [TALG 2024]提出的问题。 第三，它给出了Chudnovsky、Hajebi和Spirkl [Combinatorica 2024]已知结果的一个简洁且自洽的证明，即对于每个固定的$r$和$k$，\textsc{列表$r$-着色}在$kP_3$-自由图上是多项式时间可解的。 我们也考虑了两种自然的距离-$d$广义的\textsc{最大权重独立集}和\textsc{列表$r$-着色}，并为每个固定的整数$r$，$k$和$d \geq 6$在$kP_3$-free 图上提供了多项式时间算法。 显示英文摘要

摘要： We show that, for every fixed positive integers $r$ and $k$, \textsc{Max-Weight List $r$-Colorable Induced Subgraph} admits a polynomial-time algorithm on $kP_3$-free graphs. This problem is a common generalization of \textsc{Max-Weight Independent Set}, \textsc{Odd Cycle Transversal} and \textsc{List $r$-Coloring}, among others. Our result has several consequences. First, it implies that, for every fixed $r \geq 5$, assuming $\mathsf{P}\neq \mathsf{NP}$, \textsc{Max-Weight List $r$-Colorable Induced Subgraph} is polynomial-time solvable on $H$-free graphs if and only if $H$ is an induced subgraph of either $kP_3$ or $P_5+kP_1$, for some $k \geq 1$. Second, it makes considerable progress toward a complexity dichotomy for \textsc{Odd Cycle Transversal} on $H$-free graphs, allowing to answer a question of Agrawal, Lima, Lokshtanov, Rz{\k{a}}{\.z}ewski, Saurabh, and Sharma [TALG 2024]. Third, it gives a short and self-contained proof of the known result of Chudnovsky, Hajebi, and Spirkl [Combinatorica 2024] that \textsc{List $r$-Coloring} on $kP_3$-free graphs is polynomial-time solvable for every fixed $r$ and $k$. We also consider two natural distance-$d$ generalizations of \textsc{Max-Weight Independent Set} and \textsc{List $r$-Coloring} and provide polynomial-time algorithms on $kP_3$-free graphs for every fixed integers $r$, $k$, and $d \geq 6$.