{"id":"43f7f0bf-c8c3-4ae0-9e38-704f38a7a32f","arxiv_id":"2505.12866","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For complements of line graphs, (tw,omega)-boundedness is equivalent to bounded tree-independence number; (P3+P1)-free graphs have exact tree-independence number equal to their induced biclique number except in one special C5 case; {P4+P1,C4}-free graphs have tree-clique-cover number at most 3.","lead":"This graph theory paper proves new cases where bounded treewidth in a graph class is equivalent to bounded tree-independence number, including a full characterization for complements of line graphs. If correct, these results imply polynomial-time algorithms for Independent Set on the newly covered classes.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1.9's induction base is false as printed: the proof claims a connected triangle-free (P3+P1)-free graph has alpha at most 2, but K2,3 is a counterexample, and it also misidentifies complete multipartite graphs as chordal.","rationale":"I checked the central equivalence in Theorem 1.7 and found the proof sound: the implications are elementary and the only delicate step, Condition 5 implies Condition 4, is valid because the set of edges not incident to the unique high-degree vertex is the complement of an independent set in the complement of a line graph, hence a vertex cover, and the independence bound follows from the maximum degree of the root graph. The Reader's identified gap in Lemma 6.2 is real: in the pyramid case with P1 length 2, P2 length at least 3, and P3 length at least 2, the displayed five vertices do not induce P4+P1; however, replacing y with the predecessor of b2 on P2 gives an induced P4+P1, so the lemma is readily repairable and does not threaten Theorem 1.10. The more serious issue is in the proof of Theorem 1.9, where the base case rests on two false assertions. K2,3 is a concrete counterexample to the triangle-free branch, and the complete multipartite branch confuses a graph with its complement. Since Theorem 1.9 is featured as a main contribution, this proof gap is load-bearing, even though the statement itself may be true. The appropriate verdict remains CONDITIONAL: the paper needs a corrected proof of the base case before Theorem 1.9 can be accepted. This matches the Reader's final verdict, so no adjustment is needed, but the reason for conditionality should be updated to include the Theorem 1.9 base-case error.","tokens_in":19705,"tokens_out":45286,"duration_ms":456571,"concrete_test":"Re-derive the base case of Theorem 1.9 without the false assertion alpha(G) <= 2. Concretely, for every connected (P3+P1)-free graph G, prove directly that tree-alpha(G) <= max{ibn(G), 2}. As a minimal check, verify the two witnesses that expose the current error: K2,3, which is triangle-free, complete multipartite, non-chordal, and satisfies tree-alpha=ibn=2; and C5, which is triangle-free, C4-free, and satisfies tree-alpha=2 with ibn=1. If no such direct proof can be supplied, Theorem 1.9 remains unproven as written.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The proof of Theorem 1.9 proceeds by induction on the number of connected components of the graph G. In the base case (k=1, G connected), the proof invokes Olariu's theorem on the paw-free complement and asserts that G is either triangle-free or complete multipartite. It then claims: 'In the first case, alpha(G) <= 2' and 'in the second case, G is a disjoint union of complete graphs, hence chordal, and by Lemma 2.3 tree-alpha(G) <= 1.' Both claims are incorrect as stated. The graph K2,3 is connected, triangle-free, and (P3+P1)-free, yet alpha(K2,3)=3, so the first branch is false. For the second branch, a complete multipartite graph is not generally a disjoint union of complete graphs; its complement is. K2,3 is complete multipartite but is not chordal: it contains an induced C4, and its tree-independence number is 2, not 1. Thus the base case of the induction is unsupported. The theorem's statement may still be true -- for K2,3, tree-alpha=2 and ibn=2 -- but the printed proof does not establish it. Since Theorem 1.9 is one of the main results advertised in the abstract (a sharp equality tree-alpha = ibn for (P3+P1)-free graphs), this is a load-bearing gap in the paper's central narrative, separate from the Lemma 6.2 display issue identified by the Reader.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper contributes to the study of (tw,ω)-bounded graph classes and their relationship with bounded tree-independence number. It proves three main results: (1) Theorem 1.7, an equivalence for complements of line graphs among (tw,ω)-boundedness, bounded tree-independence number, K_{s,s}-freeness, a vertex-cover condition, and a subgraph condition on the root graph; (2) Theorem 1.8, a short proof that K_{1,t}-free graphs with no k pairwise independent cycles have bounded tree-independence number; and (3) Theorems 1.9 and 1.10, giving respectively an exact formula tree-α(G)=ibn(G) for (P3+P1)-free graphs (with a C5-exception) and tree-θ(G)≤3 for {P4+P1,C4}-free graphs. Section 3 also establishes Conjecture 1.1 for hereditary classes excluding some clique partition graph, via the Chudnovsky–Seymour splitness theorem.","tokens_in":19881,"tokens_out":35406,"duration_ms":306456,"significance":"The results are potentially significant: Theorem 1.7 gives a complete structural and algorithmic equivalence for all complements of line graphs, a natural counterpart to the earlier line-graph result. Theorem 1.9 is a sharp exact characterization that would be a valuable tool for the open {P5,K_{t,t}}-free case, and Theorem 1.10 provides a strong bound for the related {P4+P1,C4}-free class. The simplified proof of the Ahn–Gollin–Huynh–Kwon theorem is a worthwhile contribution, and the application of splitness in Section 3 is elegant. The paper is clearly organized and the arguments are largely self-contained modulo cited theorems. However, several load-bearing proof gaps, detailed below, prevent acceptance in the present form.","major_comments":[{"comment":"The induction in the proof of Theorem 1.9 is set up 'on the number k of connected components of G,' but the induction hypothesis and the step actually concern the number of connected components of the complement: the hypothesis refers to graphs 'whose complement has at most k−1 connected components,' and the step takes G 'whose complement consists of k connected components.' In the base case k=1 the proof asserts that a connected (P3+P1)-free graph is either triangle-free or complete multipartite, citing Olariu's theorem (Theorem 5.2). This is a misapplication: Olariu's theorem describes paw-free graphs, i.e., complements of (P3+P1)-free graphs, not (P3+P1)-free graphs themselves. The asserted dichotomy is false: the triangular prism (the complement of C6) is connected, (P3+P1)-free, contains a triangle, and is not complete multipartite. The two subclaims in the base case are also false: K2,3 is a connected triangle-free (P3+P1)-free graph with α(G)=3, so 'α(G)≤2' fails; and complete multipartite graphs are not generally disjoint unions of complete graphs (e.g., K2,3 is complete multipartite and not chordal). Since this base case is used to establish tree-α(G) ≤ max{ibn(G),2} for all (P3+P1)-free graphs, the proof of Theorem 1.9 is incomplete as written.","section":"Section 5, proof of Theorem 1.9"},{"comment":"The proof of Theorem 4.2 states ε_k = Ω(1/(20k)) using recurrence (1): ε_k = min{ε_{k−1}/20, δ_k/20, δ_k/(5(k+1)), 1/(30(k−2))}. This recurrence forces exponential decay: ε_k ≤ ε_{k−1}/20, so ε_k = O(20^{−k}) up to the polynomial factor in δ_k, not Ω(1/(20k)). Consequently the bound c_{k,t} = ⌊(t−1)/ε_k⌋ in Lemma 4.3 is O(t·20^k) (with modest polynomial factors), not O(20kt). The finiteness of c_{k,t} and the statement of Theorem 1.8 are unaffected, but the claimed quantitative bound, and the sentence in the proof of Theorem 1.8 that invokes c_{k,t}=O(20kt), are incorrect and should be revised.","section":"Section 4, Lemma 4.3 and Eq. (1)"},{"comment":"The displayed chain 'L(H) ∼= L(2K1,s) ∼= 2Ks ∼= Ks,s' is not correct under the notation used in the theorem. If L(·) denotes the complement of the line graph (as in the statement of Theorem 1.7), then L(2K1,s) is K_{s,s}, not 2K_s; if L(·) denotes the line graph, then L(2K1,s)=2K_s, which is not isomorphic to K_{s,s} for s≥2. The intended fact is that the complement of the line graph of 2K_{1,s} is K_{s,s}; this is true and the implication can be repaired by writing \\overline{L(2K1,s)}∼=K_{s,s}. As printed, however, the proof of a load-bearing equivalence in Theorem 1.7 contains a false isomorphism.","section":"Section 3, proof of Theorem 1.7, implication (3)⇒(5)"}],"minor_comments":[{"comment":"The phrase 'vertices adjacent to a1 and a2' in the pyramid case should read 'vertices adjacent to b1 and b2'; with that correction, the displayed five vertices do induce P4+P1 in the cases considered, so the pyramid argument is sound modulo this typo. As printed, the undefined a1,a2 make the argument ambiguous.","section":"Section 6, Lemma 6.2 (pyramid case)"},{"comment":"The proof begins 'Suppose that s ≥ 4 is an integer such that every graph in G is 2K1,s-subgraph-free,' but condition (5) may only give a smaller s; one should first replace s by max{s,4}.","section":"Section 3, proof of Theorem 1.7, implication (5)⇒(4)"},{"comment":"In the final paragraph, 'Similar properties holds' should be 'Similar properties hold.'","section":"Section 7"},{"comment":"The abstract says the paper 'settle[s] a number of cases of finitely many forbidden induced subgraphs'; the finite-constraint results proved here are Theorems 1.9 and 1.10, so the phrasing 'two cases' would be more precise.","section":"Abstract"}],"recommendation":"major_revision","confidential_remarks":"The paper is part of an established series and quotes several prior results by the same group. The main theorems are plausible, but the proof of Theorem 1.9 has a serious structural gap that will require more than a local fix, and the quantitative claim in Section 4 is mathematically incorrect. The Theorem 1.7 issue is largely notational and easily corrected. I recommend major revision rather than rejection, as the qualitative results appear likely to be true."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this is a genuine paper in the (tw,omega)-boundedness/tree-alpha program, and Theorem 1.7 (complements of line graphs) is correct and clean. But do not take Theorem 1.9 at face value: the proof as printed has a false base case, and the stress-test note is right. K2,3 is connected, triangle-free, (P3+P1)-free, with alpha = 3, so the claim \"in the first case alpha(G) <= 2\" is simply false; and a complete multipartite graph is not a disjoint union of cliques (K2,3 is complete multipartite and contains an induced C4). The induction base is unsupported. The theorem may still be true --- it checks on K2,3 and related examples --- but the printed proof does not establish it. That gap is load-bearing because Theorem 1.9 is advertised as one of the main results.\n\nWhat is actually new and good: Theorem 1.7 gives a multi-way equivalence for complements of line graphs with a short argument via the Chudnovsky-SeYMOUR k-split theorem. The new proof of the Ahn-Gollin-Huynh-Kwon bound (Theorem 1.8) is a genuine presentational improvement, and Theorem 1.10 gives a nice bound via K2,3-induced-minor-free graphs. The reader flags a gap in the pyramid case of Lemma 6.2, but I think that is a typo (a1/a2 for b1/b2); the intended case analysis works. Minor issue: in Lemma 4.3, the claimed c_{k,t}=O(20kt) does not follow because epsilon_k satisfies epsilon_k <= epsilon_{k-1}/20, so epsilon_k decays exponentially; the correct bound is O(t * 20^k), still finite. That is an easy fix.\n\nBottom line: worth a serious referee, but the referee should demand a corrected proof of Theorem 1.9. If the theorem is true, it needs a proper base case (Olariu applies to the complement, not to G). The rest of the paper can stand largely as is.","headline":"A real contribution to the (tw,omega)-boundedness/tree-alpha program, with a clean Theorem 1.7 and a useful short proof of the Ahn et al. result, but the proof of the advertised Theorem 1.9 has a false base case and needs major repair.","tokens_in":20540,"tokens_out":16066,"would_cite":true,"duration_ms":141736,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C75","05C05","05C69","05C83","05C76"],"pacs":[],"model":"deepseek-v4-flash","headline":"Complements of line graphs are governed by their bicliques: for every graph class, bounded tree-independence, $(\\mathrm{tw},\\omega)$-boundedness, and excluding some $K_{s,s}$ coincide.","keywords":["tree-independence number","treewidth","clique number","complements of line graphs","hereditary graph classes","forbidden induced subgraphs","induced biclique number","tree-clique-cover number"],"falsifier":"Build the pyramid with three internally disjoint chordless paths from an apex $a$ to the triangle $\\{b_1,b_2,b_3\\}$, with path lengths 2, 3, and 2; check whether the resulting 8-vertex graph has an induced $P_4+P_1$ or $C_4$. If it has neither, Lemma 6.2 is false and the chain from Corollary 6.3 to Theorem 1.10 breaks at that step.","tokens_in":19384,"feed_emoji":"📐","tokens_out":11592,"duration_ms":99938,"temperature":0.7,"pith_summary":"The paper continues the study of graph classes in which large treewidth can only arise from large cliques, called $(\\mathrm{tw},\\omega)$-bounded classes, and asks when this structural property is equivalent to having bounded tree-independence number, a tree-decomposition parameter that controls algorithmic tractability of independent-set style problems. Its central result is a full equivalence for complements of line graphs: for any graph class $\\mathcal{G}$, the class $\\overline{L(\\mathcal{G})}$ is $(\\mathrm{tw},\\omega)$-bounded exactly when it has bounded tree-independence number, exactly when it excludes some balanced complete bipartite graph $K_{s,s}$, and exactly when every graph in $\\mathcal{G}$ excludes $2K_{1,s}$ as a subgraph. The paper also proves sharp characterizations of the tree-independence number for $(P_3+P_1)$-free graphs and a tree-clique-cover bound for $\\{P_4+P_1,C_4\\}$-free graphs, and gives a short proof of a known theorem bounding tree-independence number for graphs excluding a fixed induced star and a fixed number of independent cycles. A sympathetic reader would care because each equivalence turns a property that is hard to compute into a simple forbidden-subgraph condition, and because bounded tree-independence number is exactly what makes independent-set problems tractable.","feed_headline":"For line-graph complements, treewidth is governed by cliques","feed_subtitle":"It turns a hard boundedness question into a checkable forbidden-subgraph condition.","key_machinery":"The load-bearing machinery is the tree-independence number $\\mathrm{tree}\\text{-}\\alpha(G)$: the minimum, over all tree decompositions, of the largest independence number of a bag. Boundedness of this parameter implies $(\\mathrm{tw},\\omega)$-boundedness but is stronger, and it is the parameter that yields polynomial-time algorithms for independent-set problems. For complements of line graphs, the argument passes through the splitness theorem for graphs excluding a clique partition graph (a disjoint union of cliques) and a complete bipartite graph, which forces the vertex set into two parts, one with bounded clique number and one with bounded independence number. The other named objects are the induced biclique number $\\mathrm{ibn}(G)$, the largest $s$ such that $K_{s,s}$ appears as an induced subgraph; the tree-clique-cover number $\\mathrm{tree}\\text{-}\\theta(G)$, the minimum over decompositions of the number of cliques needed to cover a bag; and the structural dichotomy for the four configurations---long prism, pyramid, $\\theta$, broken wheel---that characterize containing $K_{2,3}$ as an induced minor. Each of these objects converts a qualitative boundedness question into a concrete numerical parameter that can be bounded from forbidden induced subgraphs.","core_discovery":"On the paper's own terms, the central discovery is Theorem 1.7: for every graph class $\\mathcal{G}$, the following are equivalent for the class $\\overline{L(\\mathcal{G})}$ of complements of line graphs of graphs in $\\mathcal{G}$: (1) the class is $(\\mathrm{tw},\\omega)$-bounded; (2) it has bounded tree-independence number; (3) some $K_{s,s}$ is excluded as an induced subgraph; (4) every graph in the class has a vertex cover whose induced subgraph has independence number at most $s$; (5) every graph in $\\mathcal{G}$ is $2K_{1,s}$-subgraph-free for some $s$. The proof routes through a splitness theorem for graphs excluding a clique partition graph and a complete bipartite graph, together with the fact that complements of line graphs exclude $K_3+K_1$. The paper further shows that every $(P_3+P_1)$-free graph with at least one edge has tree-independence number equal to its induced biclique number $\\mathrm{ibn}(G)$, except for the $C_4$-free graphs containing an induced $C_5$, where the value is $2$. It also shows that every $\\{P_4+P_1,C_4\\}$-free graph has tree-clique-cover number at most $3$, and gives a shorter proof that $K_{1,t}$-free graphs with no $k$ independent cycles have tree-independence number bounded by a function of $k$ and $t$.","pith_inferences":["Theorem 1.7 suggests a template: whenever a hereditary class is known to be $(\\mathrm{tw},\\omega)$-bounded through a splitness argument, the same argument should yield bounded tree-independence number, so failures of the converse conjecture must come from classes that are not split in this sense.","If the open question on $K_{t,t}$-free $O_k$-free graphs has a positive answer, tree-independence number would grow at most logarithmically in the number of vertices, matching the lower bound constructed in the paper; the paper's star-free argument is a natural first step toward that regime.","A natural next step would be to improve the exponential dependence on $k$ in the new short proof to $k\\log k$, which would make the bound essentially optimal and would likely require importing the more delicate arguments the paper deliberately avoids.","The gap in the pyramid case of Lemma 6.2 is an invitation: checking the length-$(2,3,2)$ pyramid would either repair the proof of Theorem 1.10 with a short additional case or expose a counterexample requiring a different structural route."],"forward_implications":["For any class of complements of line graphs, $(\\mathrm{tw},\\omega)$-boundedness, bounded tree-independence number, and excluding a balanced biclique $K_{s,s}$ all coincide (Theorem 1.7).","The paper resolves the open equivalence conjecture for every hereditary class that excludes some clique partition graph: in such classes, $(\\mathrm{tw},\\omega)$-boundedness is equivalent to bounded tree-independence number.","For every positive integer $t$, the class of $\\{P_3+P_1,K_{t,t}\\}$-free graphs has tree-independence number at most $t$, moving the open $\\{P_5,K_{t,t}\\}$ case of the conjecture closer to resolution.","Every $\\{P_4+P_1,C_4\\}$-free graph admits a tree decomposition whose bags are unions of three cliques; in particular its tree-independence number is at most 3.","The new proof of the known bound for $K_{1,t}$-free graphs with no $k$ independent cycles shows that the dependence on $t$ is linear, matching the known result, while the dependence on $k$ is exponential rather than $k\\log k$."],"supporting_citations":[{"why":"Supplies the splitness theorem: graphs excluding a clique partition graph and a complete multipartite graph are $k$-split, the engine behind Theorem 1.7.","marker":"[14]"},{"why":"Provides the forbidden induced subgraphs of line graphs that yield the $K_3+K_1$, $K_2+3K_1$, and $C_4+2K_1$ exclusions used for complements of line graphs.","marker":"[4]"},{"why":"Establishes that bounded tree-independence number implies $(\\mathrm{tw},\\omega)$-boundedness and gives the chordal characterization used repeatedly.","marker":"[20]"},{"why":"Gives the obstruction that balanced complete bipartite graphs are not $(\\mathrm{tw},\\omega)$-bounded, used to force condition 3 in Theorem 1.7.","marker":"[19]"},{"why":"Supplies the degree-versus-cycle-rank theorems for $O_k$-free graphs with large girth that drive the short proof of Theorem 1.8.","marker":"[5]"},{"why":"Provides the characterization of paw-free graphs (each component triangle-free or complete multipartite) on which Theorem 1.9 is built.","marker":"[27]"},{"why":"Gives the lower bound $\\mathrm{tree}\\text{-}\\alpha(G) \\ge \\mathrm{ibn}(G)$ and the prior line-graph equivalence that serves as the template for Theorem 1.7.","marker":"[18]"},{"why":"States the characterization that containing $K_{2,3}$ as an induced minor is equivalent to containing a long prism, pyramid, theta, or broken wheel, used in Lemma 6.2.","marker":"[16]"},{"why":"Provides the bound $\\mathrm{tree}\\text{-}\\alpha(G) \\le 3$ for $K_{2,3}$-induced-minor-free graphs used to obtain Lemma 6.5.","marker":"[21]"},{"why":"Gives the chromatic-number bound $\\chi \\le \\max\\{\\omega,3\\}$ for $\\{2K_2,\\mathrm{gem}\\}$-free graphs, lifted to tree-clique-cover via complementation.","marker":"[6]"}],"fun_headline_variants":["In line-graph complements, treewidth is governed by biclique exclusion","Line-graph complements: tw-bounded iff bounded tree-independence","New equivalence: biclique-free line-graph complements have bounded treewidth","For line-graph complements, treewidth and cliques tied via forbidden bicliques"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"Theorem 1.10 rests on Lemma 6.2, and the printed proof of the pyramid case does not cover the case where the first path has length 2, the second has length at least 3, and the third has length at least 2; if a pyramid of that shape avoids $P_4+P_1$ and $C_4$ as induced subgraphs, then the proof of Theorem 1.10 is incomplete as written.","fun_headline_variants_meta":{"raw":{"variants":["In line-graph complements, treewidth is governed by biclique exclusion","Line-graph complements: tw-bounded iff bounded tree-independence","New equivalence: biclique-free line-graph complements have bounded treewidth","For line-graph complements, treewidth and cliques tied via forbidden bicliques"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000333,"raw_usage":{"total_tokens":1946,"prompt_tokens":1137,"completion_tokens":809,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":753,"completion_tokens_details":{"reasoning_tokens":726}},"tokens_in":753,"tokens_out":809,"duration_ms":8323,"temperature":1.0,"reasoning_tokens":726,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T20:29:07.434927+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Build the pyramid with three internally disjoint chordless paths from an apex $a$ to the triangle $\\{b_1,b_2,b_3\\}$, with path lengths 2, 3, and 2; check whether the resulting 8-vertex graph has an induced $P_4+P_1$ or $C_4$. If it has neither, Lemma 6.2 is false and the chain from Corollary 6.3 to Theorem 1.10 breaks at that step.","supporting_citations":[{"cited_title":"Chudnovsky and P","cited_arxiv_id":null,"evidence_quote":"Supplies the splitness theorem: graphs excluding a clique partition graph and a complete multipartite graph are $k$-split, the engine behind Theorem 1.7."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the forbidden induced subgraphs of line graphs that yield the $K_3+K_1$, $K_2+3K_1$, and $C_4+2K_1$ exclusions used for complements of line graphs."},{"cited_title":"Dallard, M","cited_arxiv_id":null,"evidence_quote":"Establishes that bounded tree-independence number implies $(\\mathrm{tw},\\omega)$-boundedness and gives the chordal characterization used repeatedly."},{"cited_title":"Bonamy, E","cited_arxiv_id":null,"evidence_quote":"Supplies the degree-versus-cycle-rank theorems for $O_k$-free graphs with large girth that drive the short proof of Theorem 1.8."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the characterization of paw-free graphs (each component triangle-free or complete multipartite) on which Theorem 1.9 is built."},{"cited_title":"Dallard, M","cited_arxiv_id":null,"evidence_quote":"States the characterization that containing $K_{2,3}$ as an induced minor is equivalent to containing a long prism, pyramid, theta, or broken wheel, used in Lemma 6.2."}],"review_version":1}