Pith. sign in

REVIEW 6 minor 26 references

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

T0 review · 0 major / 6 minor · reviewed 2026-08-16 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper proves that Max-Weight List $r$-Colorable Induced Subgraph can be solved in polynomial time on $kP_3$-free graphs for every fixed $r$ and $k$, and extends this to distance-$d$ analogues for $d \geq 6$.

desk verdict A genuinely new polynomial-time algorithm for max-weight list r-colorable induced subgraphs on kP3-free graphs, with a self-contained proof and a completed dichotomy for r>=5; the distance-d part is narrower and more fragile but honestly scoped. read the letter →

arxiv 2505.00412 v1 pith:PG77ABG3 submitted 2025-05-01 math.CO cs.DMcs.DS

Esther Galby , Paloma T. Lima , Andrea Munaro , Amir Nikabadi This is my paper · ORCID
classification math.COcs.DMcs.DS MSC 05C8505C1505C6968Q2568R10
keywords kP3-freegraphsMax-WeightListr-ColorableInducedSubgraphOddCycleTransversalamiablefamilydistance-dindependentsetcoloringH-freepolynomial-timealgorithm
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper proves a broad tractability result: on graphs that contain no $k$ disjoint induced copies of the three-vertex path $P_3$, the problem of finding a maximum-weight induced subgraph that admits a list $r$-coloring is solvable in polynomial time, for every fixed $r$ and $k$. This single result specializes to maximum independent set ($r=1$), odd cycle transversal ($r=2$), and list $r$-coloring, so all of these problems become polynomial-time solvable on $kP_3$-free graphs. The proof shows that such graphs admit a polynomial-size 'amiable family' of simple, clique-union vertex sets that cover every maximal independent set, and then reduces the search to a polynomial number of maximum-weight bipartite matching problems. A distance-$d$ variant of the same machinery yields polynomial-time algorithms for Max-Weight Distance-$d$ Independent Set and List $(d,r)$-Coloring for every $d \geq 6$.

What carries the argument

The load-bearing object is the amiable family and its distance-$d$ generalization. An amiable family is a polynomial-size collection of vertex subsets of a graph $G$ such that each member induces a $P_3$-free subgraph (every connected component is a clique) and every maximal independent set is contained in some member; a distance-$d$ amiable family adds the requirements that the components of each member are pairwise at distance at least $d$ in $G$ and that every maximal distance-$d$ independent set is covered. The paper proves these families exist and can be computed in polynomial time for $kP_3$-free graphs (Lemma 8, and Lemma 7 for $d \geq 6$) via an algorithm that enumerates induced $P_3$'s and recursively builds families on anti-neighborhoods, which are $(k-1)P_3$-free. The second supporting mechanism is Lemma 9, which converts an $r$-tuple of family members into an auxiliary weighted bipartite graph whose left side is the vertices of the union, whose right side is the connected components of the induced $P_3$-free subgraphs, and whose edges carry vertex weights; a maximum-weight matching then selects the best color assignment subject to lists and to each color class lying inside its designated family member.

What would settle it

A concrete check: enumerate all $kP_3$-free graphs on up to ten vertices, run the $\Gamma_k$ or $\Lambda^d_k$ construction, and verify that every maximal (distance-$d$) independent set lies in some family member; any violation refutes the containment claim. For the distance case, specifically search for a $2P_3$-free graph in which two cliques of a recursively built set are at distance exactly $d-1$ for some $d < 6$, which the inequality $2(d-3) \leq d-1$ rules out.

Watch

Extended reading notes

Core claim

The central discovery is that Max-Weight List $r$-Colorable Induced Subgraph is polynomial-time solvable on $kP_3$-free graphs for every fixed $r \geq 1$ and $k \in \mathbb{N}$, a statement the paper proves as Theorem 3 by combining two structural ingredients. First, every $kP_3$-free graph admits an amiable family: a collection of $|V(G)|^{O(k)}$ vertex subsets, each inducing a $P_3$-free subgraph (a disjoint union of cliques), such that every maximal independent set is contained in one of them; the recursive construction enumerates induced $P_3$'s and recurses on their anti-neighborhoods, which are $(k-1)P_3$-free. Second, for each $r$-tuple of family members, the problem of choosing a maximum-weight induced subgraph with a list-respecting coloring whose color classes lie in those members reduces to a maximum-weight bipartite matching problem, solved by the Hungarian method. The paper obtains distance-$d$ analogues by strengthening the family definition to require that the components of each member be pairwise at distance at least $d$ and that every maximal distance-$d$ independent set be covered; this works for every $d \geq 6$, with the threshold forced by an inequality in the containment proof.

Load-bearing premise

The algorithm is correct only if every (distance-$d$) independent set is contained in one of the polynomial many $P_3$-free containers that the recursive construction produces, and this containment is exactly what the inductive Claims (2) and (6) assert; if that proof failed for any $kP_3$-free input, an optimal color class could be missed.

Editorial extensions

If this is right

  • Odd Cycle Transversal is polynomial-time solvable on $kP_3$-free graphs for every $k$, resolving the open problem that had been posed for $(P_3+P_2)$-free graphs.
  • For every fixed $r \geq 5$, assuming $\mathsf{P} \neq \mathsf{NP}$, 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 $kP_3$ or of $P_5+kP_1$, completing the dichotomy.
  • List $r$-Coloring on $kP_3$-free graphs is polynomial-time solvable for all fixed $r$ and $k$, with a proof that is shorter and self-contained compared with the earlier proof of this result.
  • Max-Weight Distance-$d$ Independent Set and List $(d,r)$-Coloring are polynomial-time solvable on $kP_3$-free graphs for every fixed $d \geq 6$, and the only remaining open case for the independent set problem is $d=4$.
  • Toward the Odd Cycle Transversal dichotomy on $H$-free graphs, the sole remaining open case is $H = k_4P_4 + k_3P_3 + k_2P_2 + k_1P_1$ with $k_4 \geq 1$ and $k_4+k_3 \geq 2$; the specific graph $(P_4+P_3)$ is singled out as Question 10.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The matching-based reduction indicates that on $kP_3$-free graphs, list-colorable induced subgraph problems have a hidden combinatorial structure independent of standard width parameters, which are known to be unbounded even for $2P_3$-free graphs; the same template might apply to other hereditary properties closed under replacing components.
  • The $d \geq 6$ threshold is an artifact of the inequality $2(d-3) \leq d-1$ in the containment proof, so the genuinely open case $d=4$ could be settled by seeking a polynomial-size distance-$4$ amiable family; the authors suspect no such family exists.
  • A concrete testable extension is to verify the containment property computationally: enumerate all small $kP_3$-free graphs and check that every maximal (distance-$d$) independent set lies inside the constructed family, which would directly test the paper's central structural claim.
  • The amiable-family recursion could in principle be ported to other forbidden-induced-subgraph classes in which deleting the neighbourhood of a small obstruction reduces the number of forbidden copies, offering a route to new dichotomies for induced subgraph problems.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 6 minor

Summary. The paper studies Max-Weight List r-Colorable Induced Subgraph on kP3-free graphs. The main result, Theorem 3, states that for every fixed r≥1 and every k, this problem admits a polynomial-time algorithm on kP3-free graphs. The approach is to compute an amiable family of polynomial size (Lemma 8), meaning a family of P3-free induced subgraphs that jointly contain every independent set, and then reduce the problem to polynomially many maximum-weight bipartite matching instances (Lemma 9). The paper derives several consequences: a complete dichotomy for the problem on H-free graphs for r≥5 under P≠NP (Theorem 4), progress on Odd Cycle Transversal and a related open problem of Agrawal et al., and a short self-contained proof of the known polynomial-time solvability of List r-Coloring on kP3-free graphs. For distances d, the paper introduces distance-d amiable families and proves, for every fixed d≥6, polynomial-time algorithms for Max-Weight Distance-d Independent Set and List (d,r)-Coloring on kP3-free graphs (Theorems 5 and 6), with the d≥6 restriction explicitly forced by the proof in Lemma 7.

Significance. If the results hold, this is a substantial contribution to the algorithmic theory of H-free graphs. Theorem 4 completely settles the complexity of a natural list-coloring variant for r≥5, and Theorem 3 answers and generalizes a question left open by Agrawal et al. for Odd Cycle Transversal. The paper also provides a much shorter and self-contained proof of the previously technical result of Chudnovsky, Hajebi, and Spirkl. A notable strength is that the paper is transparent about its scope: it explicitly notes that no proof for k>2 existed in Lozin's prior work and supplies a full proof, and it clearly states that the distance-d theorems apply only for d≥6, with d=4 left open in Question 11. The algorithmic reductions are clean, the size bounds and running-time recurrences are explicit, and the proofs of Lemmas 8, 9, and 7 are written in enough detail to be verifiable.

minor comments (6)
  1. [Section 3, Algorithm 1] The loops "for every member S∈S do" modify S inside the loop; please specify that the enumeration is over a snapshot of S taken at the start of the iteration, otherwise the pseudocode is formally ambiguous.
  2. [Lemma 8 proof] The notation "viuw" for an induced P3 with middle vertex vi is defined, but in the later case analysis the two patterns "viuw" and "uviw" require the reader to track which vertex is the degree-2 vertex; a one-sentence reminder at the first use in the proof of Claim (2) would improve readability.
  3. [Section 4, Algorithm 2] The forbidden set (F∩N^{≥4}(u))∪(N^{≥4}(u)∩N^{≤d-1}(u)) is central to Claims (5) and (6), but it is introduced without an intuitive explanation; a short comment saying that it encodes the vertices that are either forbidden outright or too close to u would help the reader follow the recursive call.
  4. [Section 4, discussion before Lemma 7] The sentence "the failure for d∈{3,5} is to be expected given the hardness results in Theorem 2" should be qualified: Theorem 2 does not settle d=4, and the paper leaves d=4 open in Question 11; the current phrasing might suggest all d≤5 are resolved.
  5. [Lemma 7 proof] In the base cases for k=1, the text writes Λd_1(G)={V(G)\F}, but the algorithm is defined as Λd_k(G,F); please use the two-argument notation consistently.
  6. [Theorem 6 proof] The proof says "find a maximum-size induced subgraph H" while Lemma 9 is stated for weights; since all weights can be taken to be 1, this is fine, but a one-line remark would remove any ambiguity.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the central derivation is self-contained, with only minor contextual self-citations.

full rationale

The paper's main algorithm does not fit its target quantity or import its conclusion from self-citations. Lemma 8 re-proves the amiable-family existence from scratch, explicitly stating that no proof for k>2 was given in Lozin [20], and the containment induction in Claim (2) is an internal structural argument about independent sets rather than a restatement of the optimization problem. Lemma 9 reduces the list-colorable induced subgraph problem to weighted bipartite matching by a direct construction whose correctness proof is given in full; this is an algorithmic reduction, not an equation-level identity with the input. The distance-d results (Lemma 7, Theorems 5 and 6) are presented as new and are proved by their own induction on k; the d>=6 barrier is explicitly derived from the inequality 2(d-3) <= d-1 inside Claim (5), not assumed from prior work. Self-citations such as [1] and [18] are used only to cite background results or to state the open problem context, and the hardness side of the dichotomy is imported from distinct external papers ([6], [9], [12], [15]) rather than from this paper's own claims. No load-bearing step reduces to the definitions of the problem, and no fitted parameter is renamed as a prediction.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The central algorithm uses no fitted parameters. It relies on standard algorithmic results such as the Hungarian method and on structural lemmas proven in the paper, including the amiable-family existence lemma. The only external assumptions are standard complexity-theoretic ones used for the dichotomy statements.

assumptions (4)
  • standard math Weighted bipartite matching can be solved in polynomial time using the Hungarian method.
    Used in Lemma 9 as the core subroutine for the reduction; a standard algorithmic result cited to Schrijver.
  • domain assumption The input graph is finite and simple, with rational vertex weights.
    Modeling assumption for the optimization problems, stated in the introduction and preliminaries.
  • standard math The anti-neighborhood of an induced P3 in a kP3-free graph is (k-1)P3-free.
    Structural fact used throughout the inductive proofs of Lemma 8 and Lemma 7 to reduce k; it follows directly from the definition of an induced kP3.
  • domain assumption P != NP for the hardness side of the dichotomy in Theorem 4.
    The dichotomy statement is conditional on P != NP, a standard complexity-theoretic assumption; it does not affect the polynomial-time algorithms themselves.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Maximum list $r$-colorable induced subgraphs in $kP_3$-free graphs." pith.science (2026). https://pith.science/paper/PG77ABG3

@misc{pith2026250500412,
  author       = {Pith},
  title        = {Pith review of: Maximum list $r$-colorable induced subgraphs in $kP_3$-free graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/PG77ABG3}},
  note         = {Machine review of arXiv:2505.00412}
}
abstract

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$.

Figures

Figures reproduced from arXiv: 2505.00412 by the authors.

Figure 1
Figure 1. Visualization for distance-d amiable family S = {S1, S2, S3}. Circles represent cliques and α, β are maximal distance-d independent sets. Dashed lines depict paths of lengths at least d. bipartite graph where one partition class Y consists of S i∈[r] Si , the other class X consists of the connected components of the subgraphs G[Si ], for i = 1, . . . , r, and there is an edge between y ∈ Y and x ∈ X if and only if y… view at source ↗
Figure 2
Figure 2. The case d ≤ 5 (paths in blue are of length d − 3, those in red, d − 2). • Each (inclusion-wise) maximal F-avoiding distance-d independent set of G is contained in some member of S. Note that a distance-d amiable family of G is nothing but an F-avoiding distance￾d amiable family of G for F = ∅. As we shall see, our proof of Lemma 7 in fact shows that, for every kP3-free graph G and every F ⊆ V (G), the graph G admit… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

26 extracted references · 25 canonical work pages

  1. [1]

    Agrawal, P

    A. Agrawal, P. T. Lima, D. Lokshtanov, P. Rzążewski, S. Saurabh, and R. Sharma. Odd Cycle Transversal on P5-free graphs in polynomial time.ACM Transactions on Algorithms, 21(2):16:1– 16:14, 2025

    work page 2025

  2. [2]

    Bacsó, D

    G. Bacsó, D. Lokshtanov, D. Marx, M. Pilipczuk, Z. Tuza, and E. J. van Leeuwen. Subexponential- time algorithms for Maximum Independent Set in Pt-free and broom-free graphs. Algorithmica, 81(2):421–438, 2019

    work page 2019

  3. [3]

    Bergougnoux, T

    B. Bergougnoux, T. Korhonen, and I. Razgon. New width parameters for Independent Set: One- sided-mim-width and neighbor-depth. In D. Paulusma and B. Ries, editors,Graph-Theoretic Con- cepts in Computer Science - 49th International Workshop (WG 2023), volume 14093 of Lecture Notes in Computer Science, pages 72–85. Springer, 2023

    work page 2023

  4. [4]

    Bouchitté and I

    V. Bouchitté and I. Todinca. Listing all potential maximal cliques of a graph.Theoretical Computer Science, 276(1-2):17–32, 2002. 20 MAXIMUM LIST r-COLORABLE INDUCED SUBGRAPHS IN kP3-FREE GRAPHS

    work page 2002

  5. [5]

    Brettell, A

    N. Brettell, A. Munaro, D. Paulusma, and S. Yang. Comparing width parameters on graph classes. https://arxiv.org/abs/2308.05817, 2023

    arXiv 2023

  6. [6]

    Chiarelli, T

    N. Chiarelli, T. R. Hartinger, M. Johnson, M. Milanič, and D. Paulusma. Minimum connected transversals in graphs: new hardness results and tractable cases using the price of connectivity. Theoretical Computer Science, 705:75–83, 2018

    work page 2018

  7. [7]

    Chudnovsky, S

    M. Chudnovsky, S. Hajebi, and S. Spirkl. List-k-Coloring H-free graphs for allk > 4.Combinatorica, 44(5):1063–1068, 2024

    work page 2024

  8. [8]

    Chudnovsky, R

    M. Chudnovsky, R. McCarty, M. Pilipczuk, M. Pilipczuk, and P. Rzążewski. Sparse induced sub- graphs inP6-free graphs. In D. P. Woodruff, editor,Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms (SODA 2024), pages 5291–5299. SIAM, 2024

    work page 2024

Show all 26 references
  1. [9]

    Couturier, P

    J.-F. Couturier, P. A. Golovach, D. Kratsch, and D. Paulusma. List coloring in the absence of a linear forest.Algorithmica, 71:21–35, 2015

    2015

  2. [10]

    K. K. Dabrowski, C. Feghali, M. Johnson, G. Paesani, D. Paulusma, and P. Rzążewski. On cy- cle transversals and their connected variants in the absence of a small linear forest.Algorithmica, 82:2841–2866, 2020

    2020

  3. [11]

    Dallard, M

    C. Dallard, M. Krbezlija, and M. Milanič. Vertex cover at distance onH-free graphs. In P. Flocchini and L. Moura, editors,Combinatorial Algorithms - 32nd International Workshop (IWOCA 2021), volume 12757 ofLecture Notes in Computer Science, pages 237–251. Springer, 2021

    2021

  4. [12]

    H. Eto, F. Guo, and E. Miyano. Distance-d independent set problems for bipartite and chordal graphs. Journal of Combinatorial Optimization, 27(1):88–99, 2014

    2014

  5. [13]

    F. V. Fomin, I. Todinca, and Y. Villanger. Large induced subgraphs via triangulations and CMSO. SIAM Journal on Computing, 44(1):54–87, 2015

    2015

  6. [14]

    Hajebi, Y

    S. Hajebi, Y. Li, and S. Spirkl. Complexity dichotomy for List-5-Coloring with a forbidden induced subgraph. SIAM Journal on Discrete Mathematics, 36(3):2004–2027, 2022

    2004

  7. [15]

    Henderson, E

    C. Henderson, E. Smith-Roberge, S. Spirkl, and R. Whitman. Maximumk-colourable induced sub- graphs in (P5 + rK1)-free graphs. https://arxiv.org/abs/2410.08077, 2024

    2024

  8. [16]

    R. M. Karp. Reducibility among combinatorial problems. In R. E. Miller, J. W. Thatcher, and J. D. Bohlinger, editors,Complexity of Computer Computations: Proceedings of a symposium on the Complexity of Computer Computations, pages 85–103. Springer US, 1972

    1972

  9. [17]

    Journal of Computer and System Sciences, 20(2):219–230, 1980

    J.M.LewisandM.Yannakakis.Thenode-deletionproblemforhereditarypropertiesis NP-complete. Journal of Computer and System Sciences, 20(2):219–230, 1980

    1980

  10. [18]

    P. T. Lima, M. Milanič, P. Muršič, K. Okrasa, P. Rzążewski, and K. Štorgel. Tree decompositions meetinducedmatchings: BeyondMaxWeightIndependentSet.InT.M.Chan, J.Fischer, J.Iacono, and G. Herman, editors,32nd Annual European Symposium on Algorithms (ESA 2024), volume 308 of LI...

    2024

  11. [19]

    Lokshtanov, P

    D. Lokshtanov, P. Rzążewski, S. Saurabh, R. Sharma, and M. Zehavi. Maximum Partial ListH- Coloring on P5-free graphs in polynomial time.https://arxiv.org/abs/2410.21569, 2024

    2024

  12. [20]

    V. V. Lozin. From matchings to independent sets.Discrete Applied Mathematics, 231:4–14, 2017

    2017

  13. [21]

    V. V. Lozin and R. Mosca. Maximum regular induced subgraphs in2P3-free graphs. Theoretical Computer Science, 460:26–33, 2012

    2012

  14. [22]

    Milanič and N

    M. Milanič and N. Pivač. Polynomially bounding the number of minimal separators in graphs: Reductions, sufficient conditions, and a dichotomy theorem.Electronic Journal of Combinatorics, 28(1), 2021

    2021

  15. [23]

    Montealegre and I

    P. Montealegre and I. Todinca. On Distance-d Independent Set and other problems in graphs with “few” minimal separators. In P. Heggernes, editor,Graph-Theoretic Concepts in Computer Science - 42nd International Workshop (WG 2016), volume 9941 ofLecture Notes in Computer Scienc...

    2016

  16. [24]

    Paesani, D

    G. Paesani, D. Paulusma, and P. Rzążewski. Feedback Vertex Set and Even Cycle Transversal for H-free graphs: Finding large block graphs.SIAM Journal on Discrete Mathematics, 36(4):2453– 2472, 2022

    2022

  17. [25]

    Schrijver.Combinatorial Optimization - Polyhedra and Efficiency, volume 24 ofAlgorithms and Combinatorics

    A. Schrijver.Combinatorial Optimization - Polyhedra and Efficiency, volume 24 ofAlgorithms and Combinatorics. Springer, 2004

    2004

  18. [26]

    A. Sharp. Distance coloring. In L. Arge, M. Hoffmann, and E. Welzl, editors,Algorithms - ESA 2007, 15th Annual European Symposium, volume 4698 ofLecture Notes in Computer Science, pages 510–521. Springer, 2007

    2007

Pith tools

Reviewed August 16, 2026 · model on record in the stance chip above.