Pith. sign in

REVIEW 3 major objections 4 minor 1 cited by

Treewidth versus clique number. V. Further connections with tree-independence number

T0 review · 3 major / 4 minor · reviewed 2026-08-15 · deepseek-v4-flash

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

Pith's one-line read 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.

desk verdict 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. read the letter →

arxiv 2505.12866 v1 pith:K33FO4RW submitted 2025-05-19 math.CO

Claire Hilaire , Martin Milanič , {DJ}or{j̣e Vasić This is my paper · ORCID
classification math.CO MSC 05C7505C0505C6905C8305C76
keywords tree-independencenumbertreewidthcliquecomplementsoflinegraphshereditarygraphclassesforbiddeninducedsubgraphsbicliquetree-clique-cover
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

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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

Load-bearing premise

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.

Editorial extensions

If this is right

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

Reading between the lines

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

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

3 major / 4 minor

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.

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 (3)
  1. [Section 5, proof of Theorem 1.9] 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.
  2. [Section 4, Lemma 4.3 and Eq. (1)] 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.
  3. [Section 3, proof of Theorem 1.7, implication (3)⇒(5)] 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.
minor comments (4)
  1. [Section 6, Lemma 6.2 (pyramid case)] 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.
  2. [Section 3, proof of Theorem 1.7, implication (5)⇒(4)] 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}.
  3. [Section 7] In the final paragraph, 'Similar properties holds' should be 'Similar properties hold.'
  4. [Abstract] 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.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity; the central derivations reduce to external theorems and explicit constructions, though two printed proof gaps (Theorem 1.9 base case, Lemma 6.2 pyramid case) are correctness concerns, not circularity.

full rationale

The paper's derivation chain is non-circular. Theorem 1.7 is proved by direct implications: (2)->(1) via Lemma 2.1; (1)->(3) by contraposition using Lemma 2.2; (3)->(5) via the behavior of complements of line graphs under taking subgraphs; (5)->(4) via a degree argument showing the root graph has at most one high-degree vertex; and (4)->(2) by explicitly constructing a tree decomposition whose bags are S union {t}. No condition is defined in terms of another condition, and no fitted parameter is renamed as a prediction. Section 4's proof of Theorem 1.8 invokes Bonamy et al. [5] for the degree lower bound and then performs its own feedback-vertex-set and tree-decomposition argument; the cited theorem does not assume bounded tree-independence number. Section 5 uses Olariu's paw-free theorem and Lemma 5.1 (tree-alpha >= ibn) from [18]; Lemma 5.1 is a parameter-free prior theorem, not the equality being proved, and the induction is an independent argument. Section 6's Theorem 1.10 uses the K_{2,3}-induced-minor characterization of Dallard et al. [16] and the tree-alpha bound of [21]; both are published, parameter-free theorems whose assumptions do not include tree-theta-boundedness of {P4+P1,C4}-free graphs, so these self-citations are real evidence rather than circularity. The reviewer should note two genuine proof-quality gaps: the base case of Theorem 1.9 asserts alpha(G) <= 2 for connected triangle-free (P3+P1)-free graphs, but K_{2,3} is a counterexample, and the printed pyramid case of Lemma 6.2 does not cover all path-length combinations. These are correctness concerns, not instances of a claim reducing to its own input by construction.

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

The paper is a purely deductive work. It introduces no free parameters and no new postulated objects. It relies on a stack of prior theorems: Chudnovsky-Seymour k-split theorem, Olariu paw-free characterization, Dallard et al. results on tree-independence number, Bonamy et al. indefinite-cycle results, Brause et al. chromatic bound, and Dallard et al. structural characterization of K2,3-induced-minor-free graphs. Several of these come from the same authors' earlier papers in the series; they are treated as black boxes and are not the targets of this paper's derivations.

assumptions (9)
  • domain assumption Theorem 3.1 (Chudnovsky and Seymour 2014): for every clique partition graph H1 and complete multipartite graph H2, there is an integer k such that every {H1,H2}-free graph is k-split.
    Used in Theorem 3.2 to reduce hereditary classes excluding a clique partition graph to bounded splitness.
  • domain assumption Lemma 2.3 (Dallard et al. 2024): a graph is chordal if and only if tree-alpha(G) <= 1.
    Used in Theorem 1.8 (forests are chordal) and Theorem 1.9 (chordal case).
  • domain assumption Lemma 5.1 (Dallard et al. 2024): tree-alpha(G) >= ibn(G) for every graph G.
    Lower bound used in Theorem 1.9.
  • domain assumption Theorem 5.2 (Olariu 1988): a graph is paw-free if and only if each connected component is triangle-free or complete multipartite.
    Structural basis for the (P3+P1)-free analysis in Theorem 1.9, via complementation.
  • domain assumption Theorems 4.1 and 4.2 (Bonamy et al. 2024): degree-versus-cycle-rank bounds for Ok-free graphs of girth at least 11.
    Core input for the short proof of Theorem 1.8; the paper reproduces the recursion defining epsilon_k.
  • domain assumption Lemma 6.1 (Dallard et al. 2024): a graph contains K2,3 as an induced minor if and only if it contains a long prism, pyramid, theta, or broken wheel as an induced subgraph.
    Used to prove Corollary 6.3 that {P4+P1,C4}-free graphs are K2,3-induced-minor-free.
  • domain assumption Proposition 6.4 (Dallard et al. 2024): every K2,3-induced-minor-free graph has tree-alpha at most 3.
    Upper bound used in Lemma 6.5 leading to Theorem 1.10.
  • domain assumption Lemma 6.6 (Brause et al. 2019): every {2K2,gem}-free graph has chromatic number at most max{omega,3}.
    Used in Theorem 1.10 to pass from tree-alpha bound to tree-clique-cover bound.
  • domain assumption Lemma 2.2: balanced complete bipartite graphs form a class that is not (tw,omega)-bounded.
    Used in Theorem 1.7 to show that unbounded induced Ks,s forces failure of (tw,omega)-boundedness.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Treewidth versus clique number. V. Further connections with tree-independence number." pith.science (2026). https://pith.science/paper/K33FO4RW

@misc{pith2026250512866,
  author       = {Pith},
  title        = {Pith review of: Treewidth versus clique number. V. Further connections with tree-independence number},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/K33FO4RW}},
  note         = {Machine review of arXiv:2505.12866}
}
abstract

We continue the study of $(tw,\omega)$-bounded graph classes, that is, hereditary graph classes in which large treewidth is witnessed by the presence of a large clique, and the relation of this property to boundedness of the tree-independence number, a graph parameter introduced independently by Yolov in 2018 and by Dallard, Milani\v{c}, and \v{S}torgel in 2024. Dallard et al. showed that bounded tree-independence number is sufficient for $(tw,\omega)$-boundedness, and conjectured that the converse holds. While this conjecture has been recently disproved, it is still interesting to determine classes where the conjecture holds; for example, the conjecture is still open for graph classes excluding an induced star, as well as for finitely many forbidden induced subgraphs. In this paper, we identify further families of graph classes where $(tw,\omega)$-boundedness is equivalent to bounded tree-independence number. We settle a number of cases of finitely many forbidden induced subgraphs, obtain several equivalent characterizations of $(tw, \omega)$-boundedness in subclasses of the class of complements of line graphs, and give a short proof of a recent result of Ahn, Gollin, Huynh, and Kwon [SODA 2025] establishing bounded tree-independence number for graphs excluding a fixed induced star and a fixed number of independent cycles.

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. Induced packing treewidth

    math.CO 2026-07 unverdicted novelty 7.0 of 10

    Bounded induced-H-packing treewidth, a new decomposition parameter generalizing tree-independence number, yields quasipolynomial-time algorithms for MWIS, list 3-coloring, and odd cycle transversal for several choices of H.

Reference graph

Works this paper leans on

35 extracted references · 13 canonical work pages · cited by 1 Pith paper

  1. [1]

    Abrishami, B

    T. Abrishami, B. Alecu, M. Chudnovsky, S. Hajebi, S. Spirkl, and K. Vušković. Tree independence number I. (Even hole, diamond, pyramid)-free graphs.J. Graph Theory, 106(4):923–943, 2024. doi:10.1002/jgt.23104

    doi:10.1002/jgt.23104 2024

  2. [2]

    Abrishami, M

    T. Abrishami, M. Briański, J. Czyżewska, R. McCarty, M. Milanič, P. Rzążewski, and B. Walczak. Excluding a clique or a biclique in graphs of bounded induced matching treewidth.SIAM J. Discrete Math., 39(2):1189–1200, 2025.doi:10.1137/ 24M1659960

    work page 2025

  3. [3]

    J. Ahn, J. P. Gollin, T. Huynh, and O. Kwon. A coarse Erdős-Pósa theorem. In Y. Azar and D. Panigrahi, editors,Proceedings of the 2025 Annual ACM-SIAM Sym- posium on Discrete Algorithms, SODA 2025, New Orleans, LA, USA, January 12-15, 2025, pages 3363–3381. SIAM, 2025.doi:10.1137/1.9781611978322.109

    doi:10.1137/1.9781611978322.109 2025

  4. [4]

    L. W. Beineke. Characterizations of derived graphs.J. Comb. Theory, 9:129–135,

    work page

  5. [5]

    Bonamy, E

    M. Bonamy, E. Bonnet, H. Déprés, L. Esperet, C. Geniet, C. Hilaire, S. Thomassé, and A. Wesolek. Sparse graphs with bounded induced cycle packing number have logarithmic treewidth.J. Combin. Theory Ser. B, 167:215–249, 2024.doi:10.1016/ j.jctb.2024.03.003

    work page 2024

  6. [6]

    Brause, B

    C. Brause, B. Randerath, I. Schiermeyer, and E. Vumar. On the chromatic number of 2K2-free graphs. Discrete Appl. Math., 253:14–24, 2019. doi:10.1016/j.dam. 2018.09.030

    doi:10.1016/j.dam 2019

  7. [7]

    Campbell, J

    R. Campbell, J. Davies, M. Distel, B. Frederickson, J. P. Gollin, K. Hendrey, R. Hick- ingbotham, S. Wiederrecht, D. R. Wood, and L. Yepremyan. Treewidth, Hadwiger number, and induced minors. Preprint available athttps://arxiv.org/abs/2410. 19295, 2024

    work page

  8. [8]

    Chaplick, M

    S. Chaplick, M. Töpfer, J. Voborník, and P. Zeman. OnH-topological intersection graphs. Algorithmica, 83(11):3281–3318, 2021.doi:10.1007/s00453-021-00846-3

    work page doi:10.1007/s00453-021-00846-3 2021

Show all 35 references
  1. [9]

    M. Choi, C. Hilaire, M. Milanič, and S. Wiederrecht. Excluding an induced wheel minor in graphs without large induced stars. In H. Fernau and P. Kindermann, edi- tors, Graph-Theoretic Concepts in Computer Science - 51st International Workshop, WG 2025, Europäische Akademie Otz...

    2025

  2. [10]

    Chudnovsky, J

    M. Chudnovsky, J. Codsi, D. Lokshtanov, M. Milanič, and V. Sivashankar. Tree independence number V. Walls and claws. Preprint available athttps://arxiv. org/abs/2501.14658, 2025. 18

    2025 arXiv

  3. [11]

    Chudnovsky, P

    M. Chudnovsky, P. Gartland, S. Hajebi, D. Lokshtanov, and S. Spirkl. Tree inde- pendence number IV. Even-hole-free graphs. In Y. Azar and D. Panigrahi, editors, Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025, New Orleans, LA, USA, January 1...

    2025

  4. [12]

    Chudnovsky, S

    M. Chudnovsky, S. Hajebi, D. Lokshtanov, and S. T. Spirkl. Tree independence number II. Three-path-configurations. Preprint available at https://arxiv.org/ abs/2405.00265, 2024

    2024

  5. [13]

    Chudnovsky, S

    M. Chudnovsky, S. Hajebi, and N. Trotignon. Tree independence number III. Thetas, prisms and stars. Preprint available athttps://arxiv.org/abs/2406.13053, 2024

    2024

  6. [14]

    Chudnovsky and P

    M. Chudnovsky and P. Seymour. Extending the Gyárfás-Sumner conjecture. J. Comb. Theory, Ser. B, 105:11–16, 2014. doi:10.1016/j.jctb.2013.11.002

    2014 doi

  7. [15]

    Chudnovsky and N

    M. Chudnovsky and N. Trotignon. On treewidth and maximum cliques. Preprint available athttps://arxiv.org/abs/2405.07471, 2024

    2024

  8. [16]

    Dallard, M

    C. Dallard, M. Dumas, C. Hilaire, M. Milanič, A. Perez, and N. Trotignon. Detecting K2,3 as an induced minor. In A. A. Rescigno and U. Vaccaro, editors,Combinatorial Algorithms - 35th International Workshop, IWOCA 2024, Ischia, Italy, July 1-3, 2024, Proceedings, volume 14764 ...

    2024

  9. [17]

    Dallard, F

    C. Dallard, F. V. Fomin, P. A. Golovach, T. Korhonen, and M. Milanič. Computing Tree Decompositions with Small Independence Number. In K. Bringmann, M. Grohe, G. Puppis, and O. Svensson, editors,51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)...

    2024 doi

  10. [18]

    Dallard, M

    C. Dallard, M. Krnc, O. Kwon, M. Milanič, A. Munaro, K. Štorgel, and S. Wieder- recht. Treewidth versus clique number. IV. Tree-independence number of graphs ex- cluding an induced star. Preprint available athttps://arxiv.org/abs/2402.11222, 2024

    2024 arXiv

  11. [19]

    Dallard, M

    C. Dallard, M. Milanič, and K. Štorgel. Treewidth versus clique number. I. Graph classes with a forbidden structure.SIAM J. Discrete Math., 35(4):2618–2646, 2021. doi:10.1137/20M1352119

    2021 doi

  12. [20]

    Dallard, M

    C. Dallard, M. Milanič, and K. Štorgel. Treewidth versus clique number. II. Tree- independence number. Journal of Combinatorial Theory, Series B, 164:404–442,

  13. [21]

    Dallard, M

    C. Dallard, M. Milanič, and K. Štorgel. Treewidth versus clique number. III. Tree- independence number of graphs with a forbidden structure.J. Comb. Theory, Ser. B, 167:338–391, 2024. doi:10.1016/j.jctb.2024.03.005. 19

    2024 doi

  14. [22]

    Gartland

    P. Gartland. Quasi-Polynomial Time Techniques for Independent Set and Beyond in Hereditary Graph Classes. PhD thesis, University of California, Santa Barbara, USA, 2023. URL: https://www.escholarship.org/uc/item/0kk6d2jv

    2023

  15. [23]

    I. Holyer. The NP-Completeness of edge-coloring. SIAM Journal on Computing, 10(4):718–720, 1981. doi:10.1137/0210055

    1981 doi

  16. [24]

    Korhonen

    T. Korhonen. Grid induced minor theorem for graphs of small degree.J. Combin. Theory Ser. B, 160:206–214, 2023. doi:10.1016/j.jctb.2023.01.002

    2023 doi

  17. [25]

    P. T. Lima, M. Milanič, P. Mursič, K. Okrasa, P. Rzążewski, and K. Štorgel. Tree decompositions meet induced matchings: Beyond max weight independent set. In T. Chan, J. Fischer, J. Iacono, and G. Herman, editors, 32nd Annual European Symposium on Algorithms, ESA 2024, Septemb...

    2024 doi

  18. [26]

    Lozin and I

    V. Lozin and I. Razgon. Tree-width dichotomy.European J. Combin., 103:Paper No. 103517, 8, 2022. doi:10.1016/j.ejc.2022.103517

    2022

  19. [27]

    S. Olariu. Paw-free graphs. Inf. Process. Lett., 28(1):53–54, 1988. doi:10.1016/ 0020-0190(88)90143-3

    1988

  20. [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

    1929 doi

  21. [29]

    Robertson and P

    N. Robertson and P. D. Seymour. Graph minors. V. Excluding a planar graph.J. Combin. Theory Ser. B, 41(1):92–114, 1986.doi:10.1016/0095-8956(86)90030-4

    1986 doi

  22. [30]

    P. Seymour. Tree-chromatic number.J. Combin. Theory Ser. B, 116:229–237, 2016. doi:10.1016/j.jctb.2015.08.002

    2016 doi

  23. [31]

    N. Yolov. Minor-matching hypertree width. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 219–233. SIAM, Philadelphia, PA, 2018.doi:10.1137/1.9781611975031.16. 20

    2018 doi

  24. [164]

    A preprint with all proofs is available athttps://arxiv.org/ abs/2402.08332

    Springer, 2024. A preprint with all proofs is available athttps://arxiv.org/ abs/2402.08332. doi:10.1007/978-3-031-63021-7\_12

    2024 arXiv

  25. [1970]

    doi:10.1016/S0021-9800(70)80019-9

    doi

  26. [2024]

    doi:10.1016/J.JCTB.2023.10.006

    2023 doi

  27. [2025]

    doi:10.1137/1.9781611978322.151

    doi

Pith tools

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