Pith. sign in

REVIEW 1 major objections 5 minor 30 references

The paper establishes a singly exponential bound on the path number of {P_s, K_{t,t}}-free graphs in terms of clique number, and shows treedepth of such graphs is polynomial in clique number.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

T0 review · deepseek-v4-flash

2026-08-02 03:04 UTC pith:4JH5LHF6

load-bearing objection Singly exponential bound for path number in {P_s,K_{t,t}}-free graphs, with a matching lower bound, but the main theorems pass through Hajebi's unrefereed clique-polynomiality of pathwidth. the 1 major comments →

arxiv 2607.13995 v1 pith:4JH5LHF6 submitted 2026-07-15 math.CO cs.DM

Excluding paths and bicliques

Maria Chudnovsky , Julien Codsi , Matja\v{z} Krnc , Martin Milani\v{c} This is my paper
classification math.CO cs.DM MSC 05C3505C3805C7505C6905C05
keywords induced pathinduced bicliquelongest pathclique numbertreedepthhereditary graph classclique-polynomialitypathwidth
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

The paper proves that in graphs excluding a path on s vertices and a balanced biclique K_{t,t} as induced subgraphs, the maximum number of vertices in a (not necessarily induced) path is at most 2^{ω(G)^c} for a constant c depending only on s and t. This replaces the previously known doubly exponential bound with a singly exponential one and is best possible apart from the value of c. The proof passes through pathwidth: the same graph classes are shown to have pathwidth polynomial in clique number, and two new linear relationships are derived, bounding treedepth and path number by (s−1)·pw(G) and s·pw(G), respectively. Consequently, treedepth of such graphs is polynomial in clique number, and this yields the result that treedepth is clique-polynomial: any hereditary graph class where treedepth is bounded by a function of clique number in fact has a polynomial bound.

Core claim

The central claim, Theorem 2, is that for all positive integers s and t there is a constant c such that every {P_s, K_{t,t}}-free graph G satisfies pn(G) ≤ 2^{ω(G)^c}. The authors show this is tight up to the choice of c by exhibiting transitive closures of complete binary trees T_k^+, which are {P_4, K_{2,2}}-free, have clique number k and path number 2^{k+1}−1, so exponential dependence on ω is unavoidable. The proof also establishes Theorem 3, that td(G) ≤ ω(G)^c for these classes, and Theorem 4, that treedepth is clique-polynomial for all hereditary graph classes.

What carries the argument

The argument rests on three elements. First, Corollary 7, imported from a structural decomposition result and a recent theorem on pathwidth, gives that {P_s, K_{t,t}}-free graphs have pathwidth polynomial in clique number. Second, two new linear inequalities for P_s-free graphs relate the network parameters to pathwidth: Theorem 11 gives td(G) ≤ (s−1)·pw(G), and Theorem 12 gives pn(G) ≤ s·pw(G)−1, proved by induction on the order and by removing a shortest path P that hits every bag of a path decomposition, which reduces pathwidth by at least 1. Third, the transitive closures of complete binary trees provide the matching exponential lower bound for Theorem 2.

Load-bearing premise

The chain of proofs depends on Corollary 7, which asserts that {P_s, K_{t,t}}-free graphs have pathwidth polynomial in clique number; this corollary relies in turn on two imported results from the literature, one of them a recent unrefereed preprint, and if either of those fails the polynomial pathwidth bound—and with it the polynomial form of Theorems 2 and 3—collapses.

What would settle it

Exhibit a hereditary graph class in which treedepth is bounded by a function of clique number but is not polynomially bounded; this refutes Theorem 4. More directly, construct {P_s, K_{t,t}}-free graphs whose path number grows faster than 2^{ω^c} for every fixed c, contradicting Theorem 2. Also, check whether the recent unrefereed result asserting that pathwidth is clique-polynomial holds as stated; a counterexample would break Corollary 7 and the polynomial bounds of Theorems 2 and 3.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

Share X Bluesky LinkedIn Reddit HN

If this is right

  • The path number bound in Theorem 2 is the first singly exponential bound for {P_s, K_{t,t}}-free graphs, improving the doubly exponential bound that followed from a recent result on long induced paths in K_{s,s}-free graphs.
  • Theorem 3 yields a polynomial treedepth bound for these classes, making treedepth a polynomial function of clique number.
  • Theorem 4 establishes that treedepth is clique-polynomial for every hereditary graph class, mirroring the analogous result for pathwidth.
  • Theorem 12's improved relationship between path number and pathwidth yields a better bound on induced path length in graphs of bounded pathwidth: an induced path of order at least (n+1)^{1/(k−1)}−1.
  • The tightness examples show that the exponential form in Theorem 2 cannot be replaced by a subexponential bound, up to the value of c.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • A natural next step is to pin down the optimal value of c in Theorem 2; the construction only shows c must grow with s and t, not its exact rate.
  • The clique-polynomiality of treedepth suggests that algorithms whose running time depends polynomially on treedepth may run in polynomial time on any hereditary class with treedepth bounded by a function of clique number.
  • The same two-step route—structural polynomial pathwidth plus linear relationships—might generalize to other hereditary classes that exclude a finite set of graphs, or to parameters such as treewidth under additional assumptions.
  • Since Theorem 4's proof chooses s=t=2f(2), it does not give an explicit polynomial; extracting explicit exponents for natural classes would be a concrete follow-up.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

1 major / 5 minor

Summary. The paper studies graphs with no induced path P_s and no induced biclique K_{t,t}. Its main quantitative claim (Theorem 2) is that the path number satisfies pn(G) ≤ 2^{ω(G)^c}, improving the previously known doubly exponential bound obtained from Hunter et al.; a tightness example based on transitive closures of binary trees shows the exponential form is unavoidable up to the constant c. The paper further proves Theorem 3: for such graphs treedepth is bounded by a polynomial in ω(G), and derives Theorem 4, the treedepth analogue of Hajebi's clique-polynomiality of pathwidth. The proof route is: Theorem 5 gives pathwidth bounded by some function of ω; Hajebi's Theorem 6 converts this to a polynomial bound in Corollary 7; Theorem 12 converts pathwidth to path number and Theorem 11 converts pathwidth to treedepth in P_s-free graphs; Theorem 4 follows by choosing s and t to be 2^{f(2)}. The internal induction arguments appear coherent, and the main caveat is the reliance on the unrefereed Theorem 6.

Significance. Assuming the cited Hajebi theorem, the improvement from doubly exponential to singly exponential path number is a genuine quantitative advance, and the treedepth-polynomiality consequence is clean and likely to be useful. The paper is largely self-contained after Corollary 7; the induction proofs of Theorems 11 and 12 are transparent, and the binary-tree tightness example is simple and convincing. The main weakness is that the entire quantitative content is conditional on Theorem 6, a 2025 preprint whose proof is not reproduced. I do not see an internal circularity or a flaw in the reduction, but the dependence should be made explicit to the reader.

major comments (1)
  1. [§2.1, Corollary 7] All of Theorems 2–4 pass through Corollary 7, whose proof invokes Theorem 6 from the unpublished preprint [17]. The manuscript does not reproduce or independently verify Theorem 6, and this is the only route from bounded pathwidth to polynomial pathwidth. If Theorem 6 were false, Theorem 2 would reduce to the doubly exponential bound and Theorem 3 would give only a nonpolynomial treedepth bound. I do not regard this as an internal error because the attribution is clear, but the paper should state in the introduction and abstract that the main results are conditional on Hajebi's theorem, or include a proof of Theorem 6 / Corollary 7 in an appendix.
minor comments (5)
  1. [§1, Abstract] The phrase 'we improve the best known bound' may be read as an unconditional claim. Since the proof relies essentially on Theorem 6 from [17], a sentence such as 'modulo Hajebi's recent theorem' would be helpful.
  2. [§2.1, Theorem 5] The note that Theorem 5 'also follows immediately from [1,15] and [29]' would be easier to verify with one explanatory sentence, namely that Theorem 1 bounds pn(ω) and Fact 6 gives pw ≤ pn−1.
  3. [§6, Theorem 4] In the proof, the choice s = t = 2^{f(2)} should be displayed with braces; in the inline text it can be misread as 2·f(2).
  4. [§2.1, Corollary 7] The normalization of the polynomial p to one with equal positive coefficients is slightly awkward. A shorter argument using p(x) ≤ a(d+1)x^d ≤ x^{d+1} for x ≥ 2 would be clearer.
  5. [References] Reference [14] spells the name as 'Erdös'; the standard spelling is 'Erdős'.

Circularity Check

0 steps flagged

No significant circularity; main proofs rest on independent prior theorems; the sole self-citation (Theorem 5) is explicitly backed by external classical results.

full rationale

Walked the derivation chain. Theorem 2 is obtained from Corollary 7 (pw ≤ ω^c) and the internal Theorem 12 (pn ≤ s^{pw}); Theorem 3 is obtained from Corollary 7 and the internal Theorem 11 (td ≤ (s−1)pw). Corollary 7 combines two external building blocks: Theorem 5 — cited to [9] but explicitly stated to also follow immediately from [1,15] and [29] (Galvin–Rival–Sands and Robertson–Seymour are independent classical results), so the self-citation is replaceable and not load-bearing — and Theorem 6 (Hajebi), an external recent result on pathwidth clique-polynomiality. Theorem 4 reduces the treedepth analogue to Theorem 3 by a short heredity argument (choosing s=t=2f(2) and using Fact 6), which is not circular. The tightness family T_k^+ is constructed and verified in Proposition 8 without reference to the main theorems. No fitted parameter is relabeled as a prediction; no uniqueness theorem is imported from the authors; no ansatz is smuggled through citation. The only blemish is a minor proof slip in Theorem 4: the inequality s ≤ 2^{f(2)}−1 is not contradictory when f(2)≥3, although the intended contradiction s≤f(2) is immediate from td(P_s)=s and td(P_s)≤f(2); this is a correctness typo, not a circular dependency. Overall the paper is self-contained modulo two external theorems, and the score 1 reflects one minor non-load-bearing self-citation.

Axiom & Free-Parameter Ledger

0 free parameters · 4 axioms · 0 invented entities

No free parameters are fitted; the paper introduces no new entities. It relies on standard graph theory facts and two imported external theorems, the most consequential of which is Hajebi's pathwidth clique-polynomiality result.

axioms (4)
  • domain assumption Theorem 5: every {P_r,K_s,K_{t,t}}-free graph has pathwidth at most k(r,s,t).
    Used in Corollary 7 to yield a function-of-ω pathwidth bound; cited to [9] and said to also follow from [1,15,29].
  • domain assumption Theorem 6 (Hajebi): pathwidth is clique-polynomial for hereditary classes.
    Central to Corollary 7; external recent preprint (arXiv:2510.19120).
  • standard math Fact 6: ω(G) ≤ pw(G)+1 ≤ td(G) ≤ pn(G) ≤ 2^{td(G)}−1.
    Used in Theorems 11, 12, and 4 to convert between parameters.
  • standard math Erdős–Szekeres Ramsey bound in Theorem 10.
    Used in the comparison/double-exponential discussion, not in the central new theorems.

pith-pipeline@v1.3.0-alltime-deepseek · 10061 in / 18708 out tokens · 169945 ms · 2026-08-02T03:04:49.256805+00:00 · methodology

0 comments
Cite this review

Pith. "Pith review of Excluding paths and bicliques." pith.science (2026). https://pith.science/paper/4JH5LHF6

@misc{pith2026260713995,
  author       = {Pith},
  title        = {Pith review of: Excluding paths and bicliques},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/4JH5LHF6}},
  note         = {Machine review of arXiv:2607.13995}
}
Share X Bluesky LinkedIn Reddit HN
read the original abstract

Classes of graphs excluding a path and a biclique as induced subgraphs are extensively studied in the literature. One of the key structural results for such graphs is a Ramsey-type result due to Galvin, Rival, and Sands (1982), establishing the existence of a function $f$ bounding the maximum length of a path in terms of clique number $\omega$. We improve the best known bound on $f$ to a function that is a singly exponential in $\omega^c$, for some constant $c$, which we show is best possible, up to optimizing $c$. Our approach also has consequences for treedepth. In particular, we show that, for graphs excluding a path and a biclique as induced subgraphs, treedepth is bounded by a polynomial function of clique number. In turn, this result implies that every hereditary graph class that admits a function bounding treedepth of graphs in the class in terms of clique number, admits a polynomial such function. This gives a treedepth analogue of a recent result on pathwidth due to Hajebi (2025).

Figures

Figures reproduced from arXiv: 2607.13995 by Julien Codsi, Maria Chudnovsky, Martin Milani\v{c}, Matja\v{z} Krnc.

Figure 1
Figure 1. Figure 1: The graph T + k is the transitive closure of a complete binary tree of depth k. The figure depicts T + 4 . Proposition 8. Let k be a positive integer. Then: (a) For k > 1, the graph T + k is isomorphic to the graph obtained from the disjoint union of two copies of T + k−1 by adding a universal vertex. (b) T + k is traceable, that is, pn(T + k ) = |V (T + k )| = 2k − 1. (c) T + k is {P4, K2,2}-free. (d) ω(T… view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

30 extracted references · 9 canonical work pages

  1. [1]

    Lozin, and Igor Razgon

    Aistis Atminas, Vadim V. Lozin, and Igor Razgon. Linear time algo- rithm for computing a small biclique in graphs without long induced paths. InAlgorithm theory—SWAT 2012, volume 7357 ofLecture Notes in Comput. Sci., pages 142–152. Springer, Heidelberg, 2012.doi:10.1007/ 978-3-642-31155-0_13

    2012

  2. [2]

    Awesomegraphparameters

    Kenny Bešter Štorgel, Clément Dallard, Vadim Lozin, Martin Milanič, and ViktorZamaraev. Awesomegraphparameters. Preprintavailableathttps: //arxiv.org/abs/2511.05285, 2025. 11

    arXiv 2025

  3. [3]

    Pascal Gollin, Tomáš Hons, Tomáš Masařík, Martin Milanič, Paweł Rzążewski, Ondřej Suchý, and Alexandra Wesolek

    Václav Blažej, J. Pascal Gollin, Tomáš Hons, Tomáš Masařík, Martin Milanič, Paweł Rzążewski, Ondřej Suchý, and Alexandra Wesolek. Tree- independence number ofP 5-free graphs with no large bicliques. Preprint available athttps://arxiv.org/abs/2605.03965, 2026

    Pith/arXiv arXiv 2026

  4. [4]

    Bodlaender

    Hans L. Bodlaender. A partialk-arboretum of graphs with bounded treewidth.Theoret. Comput. Sci., 209(1-2):1–45, 1998.doi:10.1016/ S0304-3975(97)00228-4

    1998

  5. [5]

    On poly- nomial degree-boundedness.Adv

    Romain Bourneuf, Matija Bucić, Linda Cook, and James Davies. On poly- nomial degree-boundedness.Adv. Comb., pages Paper No. 5, 16, 2024. doi:10.19086/aic.2024.5

    work page doi:10.19086/aic.2024.5 2024

  6. [6]

    Separating polyno- mialχ-boundedness fromχ-boundedness.Combinatorica, 44(1):1–8, 2024

    Marcin Briański, James Davies, and Bartosz Walczak. Separating polyno- mialχ-boundedness fromχ-boundedness.Combinatorica, 44(1):1–8, 2024. doi:10.1007/s00493-023-00054-3

    work page doi:10.1007/s00493-023-00054-3 2024

  7. [7]

    Pascal Gollin, Martin Milanič, and Varun Sivashankar

    Maria Chudnovsky, Julien Codsi, J. Pascal Gollin, Martin Milanič, and Varun Sivashankar. Tree-independence number and forbidden induced sub- graphs: excluding a6-vertex path and a(2, t)-biclique. Preprint available athttps://arxiv.org/abs/2604.01999, 2026

    arXiv 2026

  8. [8]

    Tree independence number V

    Maria Chudnovsky, Julien Codsi, Daniel Lokshtanov, Martin Milanič, and Varun Sivashankar. Tree independence number V. Walls and claws. Preprint available athttps://arxiv.org/abs/2501.14658, 2025

    Pith/arXiv arXiv 2025

  9. [9]

    Induced sub- graphs and tree decompositions XVIII

    Maria Chudnovsky, Sepehr Hajebi, and Sophie Spirkl. Induced sub- graphs and tree decompositions XVIII. Obstructions to bounded path- width. Preprint available athttps://arxiv.org/abs/2412.17756, 2024

    Pith/arXiv arXiv 2024

  10. [10]

    On treewidth and maximum cliques.Innov

    Maria Chudnovsky and Nicolas Trotignon. On treewidth and maximum cliques.Innov. Graph Theory, 2:223–243, 2025.doi:10.5802/igt.11

    doi:10.5802/igt.11 2025

  11. [11]

    Treewidth versus clique number

    Clément Dallard, Matjaž Krnc, O-joung Kwon, Martin Milanič, Andrea Munaro, Kenny Štorgel, and Sebastian Wiederrecht. Treewidth versus clique number. IV. Tree-independence number of graphs excluding an in- duced star. Preprint available athttps://arxiv.org/abs/2402.11222, 2024

    Pith/arXiv arXiv 2024

  12. [12]

    Treewidth versus clique number

    Clément Dallard, Martin Milanič, and Kenny Štorgel. Treewidth versus clique number. II. Tree-independence number.J. Combin. Theory Ser. B, 164:404–442, 2024.doi:10.1016/j.jctb.2023.10.006

    work page doi:10.1016/j.jctb.2023.10.006 2024

  13. [13]

    Long induced paths in sparse graphs and graphs with forbidden patterns

    Julien Duron, Louis Esperet, and Jean-Florent Raymond. Long induced paths in sparse graphs and graphs with forbidden patterns. Preprint avail- able athttps://arxiv.org/abs/2411.08685, 2024

    Pith/arXiv arXiv 2024

  14. [14]

    Erdös and G

    P. Erdös and G. Szekeres. A combinatorial problem in geometry.Composi- tio Math., 2:463–470, 1935. URL:http://www.numdam.org/item?id=CM_ 1935__2__463_0. 12

    1935

  15. [15]

    Galvin, I

    F. Galvin, I. Rival, and B. Sands. A Ramsey-type theorem for trace- able graphs.J. Combin. Theory Ser. B, 33(1):7–16, 1982.doi:10.1016/ 0095-8956(82)90053-3

    1982

  16. [16]

    Induced subdivisions inKs,s-free graphs with polynomial average degree.International Mathematics Research No- tices, 2025(4):rnaf025, 02 2025.doi:10.1093/imrn/rnaf025

    António Girão and Zach Hunter. Induced subdivisions inKs,s-free graphs with polynomial average degree.International Mathematics Research No- tices, 2025(4):rnaf025, 02 2025.doi:10.1093/imrn/rnaf025

    work page doi:10.1093/imrn/rnaf025 2025

  17. [17]

    Polynomial bounds for pathwidth

    Sepehr Hajebi. Polynomial bounds for pathwidth. Preprint available at https://arxiv.org/abs/2510.19120, 2025

    arXiv 2025

  18. [18]

    Tree-alpha and excluding finitely many graphs

    Sepehr Hajebi and Sophie Spirkl. Tree-alpha and excluding finitely many graphs. Preprint available athttps://arxiv.org/abs/2605.01223, 2026

    Pith/arXiv arXiv 2026

  19. [19]

    Complexity of coloring graphs without paths and cycles.Discrete Appl

    Pavol Hell and Shenwei Huang. Complexity of coloring graphs without paths and cycles.Discrete Appl. Math., 216:211–232, 2017.doi:10.1016/ j.dam.2015.10.024

    2017

  20. [20]

    Treewidth versus clique number

    Claire Hilaire, Martin Milanič, and Ðorđe Vasić. Treewidth versus clique number. V. Further connections with tree-independence number.Journal of Graph Theory, 112(3):337–351, 2026.doi:10.1002/jgt.70036

    doi:10.1002/jgt.70036 2026

  21. [21]

    Long induced paths in minor- closed graph classes and beyond.Electron

    Claire Hilaire and Jean-Florent Raymond. Long induced paths in minor- closed graph classes and beyond.Electron. J. Combin., 30(1):Paper No. 1.18, 26, 2023.doi:10.37236/11029

    work page doi:10.37236/11029 2023

  22. [22]

    Long induced paths inK s,s-free graphs.Journal of Graph Theory, 2026

    Zach Hunter, Aleksa Milojević, Benny Sudakov, and István Tomon. Long induced paths inK s,s-free graphs.Journal of Graph Theory, 2026. To appear.doi:10.1002/jgt.70040

    work page doi:10.1002/jgt.70040 2026

  23. [23]

    A polynomial-time algorithm for the in- dependent set problem in{P 10, C4, C6}-free graphs

    Edin Husić and Martin Milanič. A polynomial-time algorithm for the in- dependent set problem in{P 10, C4, C6}-free graphs. In Ignasi Sau and Dimitrios M. Thilikos, editors,Graph-Theoretic Concepts in Computer Sci- ence - 45th International Workshop, WG 2019, Vall de Núria, Spain, June 19-21, 2019, Revised Papers, Lecture Notes in Computer Science, pages 2...

    doi:10.1007/978-3-030-30786-8 2019

  24. [24]

    Certifying coloring algorithms for graphs without long induced paths.Discrete Appl

    Marcin Kamiński and Anna Pstrucha. Certifying coloring algorithms for graphs without long induced paths.Discrete Appl. Math., 261:258–267, 2019.doi:10.1016/j.dam.2018.09.031

    doi:10.1016/j.dam.2018.09.031 2019

  25. [25]

    Lima, Martin Milanič, Peter Muršič, Karolina Okrasa, Paweł Rzążewski, and Kenny Štorgel

    Paloma T. Lima, Martin Milanič, Peter Muršič, Karolina Okrasa, Paweł Rzążewski, and Kenny Štorgel. Tree decompositions meet induced match- ings: Beyond max weight independent set.J. Comput. System Sci., 161:Pa- per No. 103819, 2026.doi:10.1016/j.jcss.2026.103819

    arXiv 2026

  26. [26]

    Some results on graphs without long induced paths.Inform

    Vadim Lozin and Dieter Rautenbach. Some results on graphs without long induced paths.Inform. Process. Lett., 88(4):167–171, 2003.doi: 10.1016/j.ipl.2003.07.004. 13

    work page doi:10.1016/j.ipl.2003.07.004 2003

  27. [27]

    Springer, Heidelberg, 2012.doi:10.1007/ 978-3-642-27875-4

    Jaroslav Nešetřil and Patrice Ossona de Mendez.Sparsity, volume 28 of Algorithms and Combinatorics. Springer, Heidelberg, 2012.doi:10.1007/ 978-3-642-27875-4

    2012

  28. [28]

    F. P. Ramsey. On a Problem of Formal Logic.Proc. London Math. Soc. (2), 30(4):264–286, 1929.doi:10.1112/plms/s2-30.1.264

    doi:10.1112/plms/s2-30.1.264 1929

  29. [29]

    Neil Robertson and P. D. Seymour. Graph minors. I. Excluding a forest.J. Combin. Theory Ser. B, 35(1):39–61, 1983.doi:10.1016/0095-8956(83) 90079-5

    work page doi:10.1016/0095-8956(83 1983

  30. [30]

    Minor-matching hypertree width

    Nikola Yolov. Minor-matching hypertree width. In Artur Czumaj, edi- tor,Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 219–233. SIAM, 2018.doi:10.1137/1.9781611975031.16. 14

    work page doi:10.1137/1.9781611975031.16 2018