Pith. sign in

REVIEW 2 major objections 4 minor 1 cited by

Graphs with no long claws: An improved bound for the analog of the Gy\'{a}rf\'{a}s' path argument

T0 review · 2 major / 4 minor · reviewed 2026-08-10 · deepseek-v4-flash

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

Pith's one-line read This paper proves that in any graph with no induced long claw $S_{t,t,t}$, one can in polynomial time either find such a claw or delete the neighborhoods of at most $3t+11$ vertices so that the remainder admits a rigid extended strip…

desk verdict Constant-size separator for S_{t,t,t}-free graphs replaces O(log n) paths; proof is sound, with minor expositional fixes needed. read the letter →

arxiv 2501.13907 v1 pith:STUQHVCU submitted 2025-01-23 math.CO cs.DMcs.DS

Romain Bourneuf , Jana Masaříková , Wojciech Nadara , Marcin Pilipczuk This is my paper · ORCID
classification math.COcs.DMcs.DS MSC 05C6905C8505C7568Q25
keywords S_{ttt}-freegraphslongclawsGyárfáspathargumentextendedstripdecompositionMaximumWeightIndependentSetthree-in-a-treeconstant-sizeseparator
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 that the Gyárfás path argument for graphs with no long claw $S_{t,t,t}$ can be sharpened from a logarithmic to a constant number of vertex deletions. The main theorem gives a polynomial-time procedure that, for any fixed $t$, either outputs an induced copy of $S_{t,t,t}$ or finds a set $S$ of at most $3t+11$ vertices such that $G-N[S]$ admits a rigid extended strip decomposition whose every particle has weight at most $w(V)/2$. Because particles behave like connected components for the Maximum Weight Independent Set problem, this reduces the recursive divide-and-conquer overhead in algorithms for $S_{t,t,t}$-free graphs: it removes one logarithmic factor from the exponent of the known quasipolynomial algorithm and makes polynomial-time algorithms for bounded-degree and sparse cases immediate. The improvement comes from inspecting the last two vertices of a minimal Gyárfás path and controlling the interaction between the big component and the big particle of the returned decomposition.

What carries the argument

The central objects are the extended strip decomposition (ESD), a partition of the graph into particles attached to vertices, edges, and triangles of an auxiliary graph $H$ that generalizes connected components, and the Gyárfás path $Q$, a minimal induced path whose closed-neighbourhood removal leaves only connected components of weight at most half. The argument is carried by three lemmas: Lemma 7 bounds the neighbourhood of a full-edge particle by neighbourhoods of two of its vertices; Lemma 10 forces any induced path between peripheral vertices of an ESD to lie in the union of edge particles and to meet each interface in at most one vertex; and Lemma 8 rigidifies a refined ESD without increasing particle weight, at the cost of possibly returning a two-vertex set whose neighbourhood removal splits the graph. The three-in-a-tree theorem supplies the ESD or the induced claw, and the final bound $|S|\le 3t+11$ comes from counting the selected vertices: $3t+3$ from the three subpaths, at most $4$ from the path–particle interface, at most $2$ from Lemma 7, plus $\ell$ and $z'$.

What would settle it

Find a graph $G$ with an extended strip decomposition $(H,\eta)$ and an induced path $Q$ between two peripheral vertices such that $Q$ uses a vertex outside $\bigcup_{e\in E(H)}\eta(e)$ or has two vertices in $\eta(e,a)$ for some edge $e=ab$; Lemma 10 forbids both, and the proof of Theorem 3 would collapse.

Watch

Extended reading notes

Core claim

The paper's central claim is Theorem 3: given a graph $G=(V,E)$ with nonnegative vertex weights and an integer $t\ge 1$, one can in polynomial time either output an induced copy of $S_{t,t,t}$ or output a set $S$ with $|S|\le 3t+11$ and a rigid extended strip decomposition of $G-N[S]$ in which every particle has weight at most $w(V)/2$. This improves the earlier result [22], which required $O(\log n)$ induced paths and hence $O(\log n)$ neighborhoods. The proof runs a minimal Gyárfás path $Q$; if $Q$ is short it is taken as $S$, otherwise it selects three vertices $x,y,z$ on $Q$ at prescribed distances, deletes neighborhoods of three $t$-vertex subpaths, and invokes the three-in-a-tree theorem to obtain either an induced $S_{t,t,t}$ or an extended strip decomposition of the remaining graph. A structural lemma (Lemma 10) — induced paths between peripheral vertices stay inside edge particles and meet each interface at most once — is used to show that a big particle can be separated from the rest by at most four vertices from $Q$, two further vertices, and the last vertex $\ell$ and its predecessor $z'$, giving the constant bound.

Load-bearing premise

The proof depends on Lemma 10, which asserts that an induced path between two peripheral vertices of an extended strip decomposition lies entirely inside edge particles and meets each interface in at most one vertex; if that lemma fails, the constant $3t+11$ does not follow from this argument.

Editorial extensions

If this is right

  • For fixed $t$, the polynomial-time algorithm for Maximum Weight Independent Set in $S_{t,t,t}$-free graphs of bounded degree follows immediately from Theorem 3: branch on $N[S]$, recurse on the particles of the ESD.
  • The algorithm for $S_{t,t,t}$-free graphs that exclude a fixed biclique $K_{s,s}$ as a subgraph can be simplified, since the constant-size separator replaces the logarithmic one.
  • Using Theorem 3 inside the quasipolynomial-time algorithm for $S_{t,t,t}$-free graphs removes one logarithmic factor from the running-time exponent.
  • The structural statement holds for every fixed $t$ with a polynomial-time algorithm, so the separator size $3t+11$ depends only on $t$, not on $n$.

Reading between the lines

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

  • The technique suggests that the three-in-a-tree black box may be avoidable in this context; a purely combinatorial argument bounding the interface between a Gyárfás path and an ESD could reduce the additive constant and the dependence on $t$.
  • The same last-two-vertices observation might extend to subdivided claws $S_{a,b,c}$ with unequal path lengths, giving constant-size separators for broader hereditary classes where the three-in-a-tree output is still an ESD.
  • Because the separator size is independent of $n$, the result hints that $S_{t,t,t}$-free graphs have bounded tree-independence number after deleting a constant number of neighborhoods, which if true would connect to other decomposition-based algorithms.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 4 minor

Summary. The paper proves Theorem 3: for every fixed integer t ≥ 1, given a vertex-weighted graph G and an integer t, one can in polynomial time either find an induced copy of the long claw S_{t,t,t} or output a set S of at most 3t+11 vertices such that G − N[S] admits a rigid extended strip decomposition in which every particle has weight at most half the total weight of V(G). This improves the O(log n) bound from Majewski et al. [22] to a constant, and the authors argue that this removes a logarithmic factor in the exponent of the quasipolynomial-time MWIS algorithm for S_{t,t,t}-free graphs and simplifies the polynomial-time algorithms of [3]. The proof refines the Gyárfás-path argument, uses the three-in-a-tree theorem (Theorem 5), and relies on a structural lemma (Lemma 10) about induced paths between peripheral vertices in extended strip decompositions.

Significance. If correct, the result is a clean and useful structural improvement: it turns a logarithmic number of deleted neighborhoods into a constant number, which is the right order of magnitude for this type of separator statement. The proof is largely self-contained modulo the Gyárfás path theorem and the three-in-a-tree theorem, and it gives an explicit constant 3t+11 and a polynomial-time algorithm. The paper also honestly mentions the independent related work [9]. The main concern is a gap in the treatment of isolated vertex particles in the extended strip decomposition; this does not appear to threaten the truth of the theorem, but it is load-bearing in the written proof and needs to be repaired before the paper can be accepted.

major comments (2)
  1. [Section 3.2, proof of Theorem 3, paragraph beginning "Suppose now that there exists a particle A..."] The claim "Since Q is a path between peripheral vertices then N_G[V(Q)] ∩ η(p) = ∅" is not correct as stated. The Gyárfás path Q has endpoints x and ℓ, and ℓ is not peripheral in the extended strip decomposition (H,η) of (G′, {x,y,z}); moreover, the vertex z′ ∈ V(Q) is not present in G′ and may be adjacent to η(p) in G. Consequently the conclusion w(η(p)) ≤ w(V)/2 is not established. This conclusion is used to justify the reduction "Since every nontrivial particle is contained in a full edge particle we can assume without loss of generality that A is a full edge particle." Without this reduction, the proof does not cover the case where the heavy particle is an isolated vertex particle, and the subsequent Claims 12 and 13 as well as the final bound |S| ≤ 3t+11 all rely on A being a full edge particle. The gap seems repairable by a direct argument for isolated vertex particles (all their neighbors in G lie in N[Y ∪ {z′}], so after removing those neighborhoods the Gyárfás property can be applied), but the current text does not supply that argument.
  2. [Section 3.2, proof of Theorem 3, same paragraph] The WLOG assumption that for every isolated p ∈ V(H) the set G[η(p)] is connected is stated without proof. The intended justification is presumably that one may split p into several isolated vertices, one for each connected component of G[η(p)], which preserves all extended strip decomposition properties and rigidity. This should be stated explicitly, because the subsequent weight bound w(η(p)) ≤ w(V)/2 depends on η(p) being a single connected component of G − N[V(Q)].
minor comments (4)
  1. [Lemma 10, last line of the proof] The expression "x_i x_{j′} ∈ E(H)" should be "x_i x_{j′} ∈ E(G)"; the edge is in the original graph, not in H.
  2. [Corollary 11, proof] The inference "η(pq,p) ≠ {z} and η(pq,q) ≠ {z} so z ∉ η(pq)" is terse. The missing justification is that if z were in η(pq), then since z is peripheral, one of the two interfaces would be exactly {z}; this would contradict the existence of the endpoint v_p ∈ V(Q1) ∩ η(pq,p) from Corollary 11, because z ∉ V(Q1).
  3. [Section 3.2, proof of Theorem 3, paragraph before Claim 12] The sentence "Since Q is a path between peripheral vertices" appears to be a typo. The path Q itself does not have two peripheral endpoints in (H,η); only Q1 (between x and y) and Q2 (starting at z) have peripheral endpoints. Please rephrase to avoid ambiguity.
  4. [Section 3.2, proof of Theorem 3, after Claim 12] When defining X = N_{G′}[A] ∩ V(Q1), the proof says that if three vertices of Q1 lie in three distinct interfaces incident to the same endpoint of pq, then they form a triangle. This is correct by property 2 of Definition 4, but the connection to the induced path Q1 should be made explicit, as a path cannot contain a triangle.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity identified: the proof rests on external Gyárfás-path and three-in-a-tree theorems, and every auxiliary structural lemma is proved in-paper.

full rationale

Theorem 3 is derived from two genuinely external black boxes: Theorem 1 (the Gyárfás path argument) and Theorem 5 (the three-in-a-tree theorem of Chudnovsky and Seymour). The constant 3t+11 is not fitted; it is accumulated from explicit sets: Y has size 3t+3, X is proven to have size at most 4 via Lemma 10, XA has size at most 2 via Lemma 7, and the two extra vertices ℓ and z' are added. Lemma 10, the main load-bearing structural statement, is proved directly from Definition 4 and does not assume any result from [22]. Lemma 7 cites [22, Observation 8] but includes a complete proof, so the citation is not load-bearing. Theorem 2 of [22] is presented as context and motivation, not used as a premise in the proof of Theorem 3. There is no fitted input renamed as a prediction and no term that is defined in terms of the very quantity it is used to derive. The paper even notes an independent concurrent result [9], which further confirms that the contribution is not an artifact of a self-citation chain. Minor expositional slips in the proof do not make the argument circular.

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

No free parameters are fitted to data; the only constants (t, 3t+11) are structural. The theorem relies on two heavy external results from prior literature (Gyárfás path argument and three-in-a-tree theorem) and on the standard extended strip decomposition framework. No new entities are postulated. The in-paper WLOG about connected isolated particles is a small proof detail, not an external axiom.

assumptions (3)
  • domain assumption Gyárfás path argument (Theorem 1): every weighted graph admits an induced path Q such that every component of G-N[V(Q)] has weight at most half of w(V), and one can choose Q minimal.
    Imported from [8]. The proof of Theorem 3 starts with such a Q and uses the minimality property to assert that deleting the neighborhood of the last vertex creates a component of weight above half.
  • domain assumption Three-in-a-tree theorem (Theorem 5): for any |Z|>=2, in polynomial time one finds either an induced subtree containing at least three terminals or a rigid extended strip decomposition of (G,Z).
    Imported from Chudnovsky and Seymour [12] with running time by Lai, Lu, and Thorup [20]. It produces the rigid extended strip decomposition (H,eta) with x,y,z peripheral.
  • domain assumption Extended strip decomposition framework, including particles, rigidity, and peripheral vertices, from the Chudnovsky-Seymour claw-free graph project.
    The statement of Theorem 3 and the proof use this framework as defined in [11,12] and [22]; the paper builds on it without re-deriving it.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Graphs with no long claws: An improved bound for the analog of the Gy\'{a}rf\'{a}s' path argument." pith.science (2026). https://pith.science/paper/STUQHVCU

@misc{pith2026250113907,
  author       = {Pith},
  title        = {Pith review of: Graphs with no long claws: An improved bound for the analog of the Gy\'arf\'as' path argument},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/STUQHVCU}},
  note         = {Machine review of arXiv:2501.13907}
}
abstract

For a fixed integer $t \geq 1$, a ($t$-)long claw, denoted $S_{t,t,t}$, is the unique tree with three leaves, each at distance exactly $t$ from the vertex of degree three. Majewski et al. [ICALP 2022, ACM ToCT 2024] proved an analog of the Gy\'{a}rf\'{a}s' path argument for $S_{t,t,t}$-free graphs: given an $n$-vertex $S_{t,t,t}$-free graph, one can delete neighborhoods of $\mathcal{O}(\log n)$ vertices so that the remainder admits an extended strip decomposition (an appropriate generalization of partition into connected components) into particles of multiplicatively smaller size. This statement has proven to be very useful in designing quasi-polynomial time algorithms for Maximum Weight Independent Set and related problems in $S_{t,t,t}$-free graphs. In this work, we refine the argument of Majewski et al. and show that a constant number of neighborhoods suffice.

Figures

Figures reproduced from arXiv: 2501.13907 by the authors.

Figure 1
Figure 1. Notations from the proof of Theorem 3. |Qx| = |Qy| = |Qz| = t + 1. • If 0 < i < j < k. We recall that xi ∈ η(e, a) − η(e, b) and xj ∈ η(e, b) − η(e, a). As xi ∈ η(e, a)−η(e, b), we can use the same reasoning as in the 0 < i = j < k case to argue that xi+1 ∈ η(e) (which operated under the same assumption that 0 < i and xi ∈ η(e, a) − η(e, b), but excluded the possibility that xi+1 ∈ η(e). That again completes the arg… view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Tree independence number V. Walls and claws

    math.CO 2025-01 conditional novelty 7.0 of 10

    For every fixed t, L_t ∪ {S_t,t,t,K_t,t}-free n-vertex graphs have tree independence number O(log^4 n).

Reference graph

Works this paper leans on

28 extracted references · 16 canonical work pages · cited by 1 Pith paper

  1. [22]

    Max Weight Independent Set in Graphs with No Long Claws: An Analog of the Gyárfás’ Path Argument.The ACM Transactions on Compu- tation Theory, 16(2), mar 2024.doi:10.1145/3636422

    Konrad Majewski, Tomáš Masařík, Jana Masaříková, Karolina Okrasa, Marcin Pilipczuk, Paweł Rzążewski, and Marek Sokołowski. Max Weight Independent Set in Graphs with No Long Claws: An Analog of the Gyárfás’ Path Argument.The ACM Transactions on Compu- tation Theory, 16(2), mar 2024.doi:10.1145/3636422

    work page doi:10.1145/3636422 2024

  2. [9]

    Tree independence number V

    Maria Chudnovsky, Julien Codsi, Martin Milanič, Daniel Lokshtanov, and Varun Sivashankar. Tree independence number V. Walls and claws, 2025

    work page 2025

  3. [3]

    Max weight in- dependent set in sparse graphs with no long claws

    Tara Abrishami, Maria Chudnovsky, Marcin Pilipczuk, and Paweł Rzążewski. Max weight in- dependent set in sparse graphs with no long claws. In Olaf Beyersdorff, Mamadou Moustapha Kanté, Orna Kupferman, and Daniel Lokshtanov, editors,41st International Symposium on Theoretical Aspects of Computer Science, STACS 2024, March 12-14, 2024, Clermont-Ferrand, Fra...

    work page doi:10.4230/lipics.stacs.2 2024

  4. [1]

    Polynomial-time algorithm for maximum independent set in bounded-degree graphs with no long induced claws

    Tara Abrishami, Maria Chudnovsky, Cemil Dibek, and Paweł Rzążewski. Polynomial-time algorithm for maximum independent set in bounded-degree graphs with no long induced claws. In Niv Buchbinder Joseph (Seffi) Naor, editor,Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference, January 9-12, 2022, pages 1448–

    work page 2022

  5. [2]

    Graphs with polynomially many minimal separators.J

    Tara Abrishami, Maria Chudnovsky, Cemil Dibek, Stéphan Thomassé, Nicolas Trotignon, and Kristina Vušković. Graphs with polynomially many minimal separators.J. Comb. Theory, Ser. B, 152:248–280, 2022. doi:10.1016/j.jctb.2021.10.003. 12

    work page doi:10.1016/j.jctb.2021.10.003 2022

  6. [4]

    Sey- mour

    Tara Abrishami, Maria Chudnovsky, Marcin Pilipczuk, Paweł Rzążewski, and Paul D. Sey- mour. Induced subgraphs of bounded treewidth and the container method. In Dániel Marx, editor,Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021 , pages 1948–1964. SIAM, 2021. doi: 10.1137/1.9781611976465.116

    work page doi:10.1137/1.9781611976465.116 2021

  7. [5]

    Alekseev

    Vladimir E. Alekseev. The effect of local constraints on the complexity of determination of the graph independence number. Combinatorial-algebraic methods in applied mathematics, pages 3–13, 1982

    work page 1982

  8. [6]

    Alekseev

    Vladimir E. Alekseev. On easy and hard hereditary classes of graphs with respect to the independent set problem. Discret. Appl. Math., 132(1-3):17–26, 2003. doi:10.1016/ S0166-218X(03)00387-1

    work page 2003

Show all 28 references
  1. [7]

    Alekseev

    Vladimir E. Alekseev. Polynomial algorithm for finding the largest independent sets in graphs without forks. Discrete Applied Mathematics, 135(1):3 – 16, 2004. Russian Translations II. URL: http://www.sciencedirect.com/science/article/pii/S0166218X02002901, doi:10. 1016/S0166-...

    2004

  2. [8]

    Subexponential-time algorithms for Maximum Independent Set inPt-free and broom-free graphs

    Gábor Bacsó, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Zsolt Tuza, and Erik Jan van Leeuwen. Subexponential-time algorithms for Maximum Independent Set inPt-free and broom-free graphs. Algorithmica, 81(2):421–438, 2019. doi:10.1007/s00453-018-0479-5

    2019 doi

  3. [10]

    Quasi- polynomial time approximation schemes for the Maximum Weight Independent Set Prob- lem in H-free graphs

    Maria Chudnovsky, Marcin Pilipczuk, Michał Pilipczuk, and Stéphan Thomassé. Quasi- polynomial time approximation schemes for the Maximum Weight Independent Set Prob- lem in H-free graphs. SIAM Journal on Computing, 53(1):47–86, 2024. arXiv:https: //doi.org/10.1137/20M1333778i,...

    2024 doi

  4. [11]

    Maria Chudnovsky and Paul D. Seymour. The structure of claw-free graphs. In Brid- get S. Webb, editor, Surveys in Combinatorics, 2005 [invited lectures from the Twentieth British Combinatorial Conference, Durham, UK, July 2005], volume 327 of London Math- ematical Society Lect...

    2005 doi

  5. [12]

    Maria Chudnovsky and Paul D. Seymour. The three-in-a-tree problem.Comb., 30(4):387–417,

  6. [13]

    Independent set onPk-free graphs in quasi-polynomial time

    Peter Gartland and Daniel Lokshtanov. Independent set onPk-free graphs in quasi-polynomial time. In Sandy Irani, editor, 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 613–624. IEEE, 2020. doi:10.1109/FOCS...

    2020

  7. [14]

    Maximum weight independent set in graphs with no long claws in quasi- polynomial time

    Peter Gartland, Daniel Lokshtanov, Tomáš Masařík, Marcin Pilipczuk, Michał Pilipczuk, and Paweł Rzążewski. Maximum weight independent set in graphs with no long claws in quasi- polynomial time. In Bojan Mohar, Igor Shinkar, and Ryan O’Donnell, editors,Proceedings of the 56th A...

    2024

  8. [15]

    Finding large induced sparse subgraphs inC>t-free graphs in quasipolynomial time

    Peter Gartland, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, and Paweł Rzążewski. Finding large induced sparse subgraphs inC>t-free graphs in quasipolynomial time. In Samir Khuller and Virginia Vassilevska Williams, editors,STOC ’21: 53rd Annual ACM SIGACT Symposium ...

    2021

  9. [16]

    Polynomial-time algorithm for Maximum Weight Independent Set onP6-free graphs

    Andrzej Grzesik, Tereza Klimošová, Marcin Pilipczuk, and Michał Pilipczuk. Polynomial-time algorithm for Maximum Weight Independent Set onP6-free graphs. In Timothy M. Chan, editor, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San D...

    2019 doi

  10. [17]

    On Ramsey covering-numbers

    András Gyárfás. On Ramsey covering-numbers. InInfinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdős on his 60th birthday), Vol. II, number 10 in Colloq. Math. Soc. Janos Bolyai, pages 801–816. North-Holland, Amsterdam, 1975

    1973

  11. [18]

    Problems from the world surrounding perfect graphs

    András Gyárfás. Problems from the world surrounding perfect graphs. InProceedings of the International Conference on Combinatorial Analysis and its Applications, (Pokrzywna, 1985), number 19 in Zastos. Mat., pages 413–441, 1987.doi:10.4064/am-19-3-4-413-441

    1985 doi

  12. [19]

    Clique is hard to approximate withinn1−ε

    Johan Håstad. Clique is hard to approximate withinn1−ε. Acta Math., 182(1):105–142, 1999. doi:10.1007/BF02392825

    1999 doi

  13. [20]

    Three-in-a-tree in near linear time

    Kai-Yuan Lai, Hsueh-I Lu, and Mikkel Thorup. Three-in-a-tree in near linear time. In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chica...

    2020

  14. [21]

    Independent set inP5-free graphs in polynomial time

    Daniel Lokshantov, Martin Vatshelle, and Yngve Villanger. Independent set inP5-free graphs in polynomial time. In Chandra Chekuri, editor,Proceedings of the Twenty-Fifth Annual ACM- SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pag...

    2014 doi

  15. [23]

    George J. Minty. On maximal independent sets of vertices in claw-free graphs.Journal of Combinatorial Theory, Series B, 28(3):284–304, 1980. doi:10.1016/0095-8956(80)90074-X

    1980 doi

  16. [24]

    Quasi-polynomial-time algo- rithm for independent set in Pt-free graphs via shrinking the space of induced paths

    Marcin Pilipczuk, Michał Pilipczuk, and Paweł Rzążewski. Quasi-polynomial-time algo- rithm for independent set in Pt-free graphs via shrinking the space of induced paths. In Hung Viet Le and Valerie King, editors,4th Symposium on Simplicity in Algorithms, SOSA 14 2021, Virtual...

    2021 doi

  17. [25]

    Algorithme de recherche d’un stable de cardinalite maximum dans un graphe sans etoile

    Najiba Sbihi. Algorithme de recherche d’un stable de cardinalite maximum dans un graphe sans etoile. Discrete Mathematics, 29(1):53–76, 1980. doi:10.1016/0012-365X(90)90287-R

    1980 doi

  18. [26]

    Linear degree extractors and the inapproximability of Max Clique and Chro- matic Number.Theory of Computing, 3(1):103–128, 2007.doi:10.4086/toc.2007.v003a006

    David Zuckerman. Linear degree extractors and the inapproximability of Max Clique and Chro- matic Number.Theory of Computing, 3(1):103–128, 2007.doi:10.4086/toc.2007.v003a006. 15

    2007 doi

  19. [1470]

    doi:10.1137/1.9781611977073.61

    SIAM, 2022. doi:10.1137/1.9781611977073.61

    2022 doi

  20. [2010]

    doi:10.1007/s00493-010-2334-4

    doi

Pith tools

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