Induced subgraphs and tree decompositions XV. Even-hole-free graphs with bounded clique number have logarithmic treewidth.

Transactions of the American Mathematical Society · 2026-05-07

We prove that for every integer $t\geq 1$ there exists an integer $c_t\geq 1$ such that every $n$-vertex even-hole-free graph with no clique of size $t$ has treewidth at most $c_t\log{n}$. This resolves a conjecture of Sintiari and Trotignon, who also proved that the logarithmic bound is asymptotically best possible. It follows that several \textsf{NP}-hard problems such as \textsc{Stable Set}, \textsc{Vertex Cover}, \textsc{Dominating Set} and \textsc{Coloring} admit polynomial-time algorithms on this class of graphs. As a consequence, for every positive integer $r$, $r$-{\sc Coloring} can be solved in polynomial time on even-hole-free graphs without any assumptions on clique size. As part of the proof, we show that there is an integer $d$ such that every even-hole-free graph has a balanced separator which is contained in the (closed) neighborhood of at most $d$ vertices. This is of independent interest; for instance, it implies the existence of efficient approximation algorithms for certain \textsf{NP}-hard problems while restricted to the class of all even-hole-free graphs.

On prime Cayley graphs

Journal of Combinatorics · 2026-01-01

The decomposition of complex networks into smaller, interconnected components is a central challenge in network theory with a wide range of potential applications. In this paper, we utilize tools from group theory and ring theory to study this problem when the network is a Cayley graph. In particular, we answer the following question: Which Cayley graphs are prime?

The Vertex Sets of Subtrees of a Tree

The Electronic Journal of Combinatorics · 2026-04-14

Let $\mathcal{F}$ be a set of subsets of a set $W$. When is there a tree $T$ with vertex set $W$ such that each member of $\mathcal{F}$ is the set of vertices of a subtree of $T$? It is necessary that $\mathcal{F}$ has the Helly property and the intersection graph of $\mathcal{F}$ is chordal. We will show that these two necessary conditions are together sufficient in the finite case, and more generally, they are sufficient if no element of $W$ belongs to infinitely many infinite sets in $\mathcal{F}$.

Dominated balanced separators in wheel-induced-minor-free graphs

ArXiv.org · 2025-12-13

Gartland and Lokshtanov conjectured that every graph that excludes some planar graph as an induced minor has a balanced separator, that is, a separator whose deletion leaves every component with no more than half of the vertices of the graph, which is dominated by a bounded number of vertices. We confirm this conjecture for excluding any fixed wheel, that is, a cycle together with a universal vertex, as an induced minor.

Coarse Balanced Separators and Tree-Decompositions

ArXiv.org · 2025-05-10

A classical result of Robertson and Seymour (1986) states that the treewidth of a graph is linearly tied to its separation number: the smallest integer $k$ such that, for every weighting of the vertices, the graph admits a balanced separator of size at most $k$. Motivated by recent progress on coarse treewidth, Abrishami, Czyżewska, Kluk, Pilipczuk, Pilipczuk, and Rzążewski (2025) conjectured a coarse analogue to this result: every graph that has a balanced separator consisting of a bounded number of balls of bounded radius is quasi-isometric to a graph with bounded treewidth. In this paper, we confirm their conjecture for $K_{t,t}$-induced-subgraph-free graphs when the separator consists of a bounded number of balls of radius $1$. In doing so, we bridge two important conjectures concerning the structure of graphs that exclude a planar graph as an induced minor.

Tree independence number II. Three-path-configurations

Journal of Combinatorial Theory Series B · 2025-09-08 · 1 citations

Induced subgraphs and tree decompositions IX. Grid theorem for perforated graphs

Advances in Combinatorics · 2025-02-19

A classical result of Erdős and Pósa states that every graph that does not contain a union of constantly many cycles as a subgraph has bounded treewidth. The authors of the present paper study the induced version of the problem: what can be said about the treewidth of graphs that do not contain a union of $c$ cycles as an *induced subgraph* (or equivalently, that do not contain $c$ disjoint cycles with no edges between them)? Note that complete graphs and complete bipartite graphs do not contain the union of 2 cycles as an induced subgraph, and they have arbitrarily large treewidth; so they need to be excluded as well. Several structure theorems on graphs of bounded treewidth also require the exclusion of grids or line-graphs of grids as an induced subgraph, but here this is not needed, as any sufficiently large grid or line-graph of a grid contains a union of many cycles as an induced subgraph. It was proved in [this paper](https://arxiv.org/abs/2206.00594) that graphs on $n$ vertices that do not contain a union of $c$ cycles, nor the complete graph $K_c$ and the complete bipartite graph $K_{c,c}$ as induced subgraphs have treewidth logarithmic in $n$. Moreover this logarithmic bound is best possible, as shown by an explicit construction (let us call this a $c$-occultation). The main result of the present paper is that if in addition to a union of $c$ cycles, the complete graph $K_c$ and the complete bipartite graph $K_{c,c}$ we forbid a $c$-occultation (or more precisely a generalized version of the orginal construction) as an induced subgraph, then the graphs under consideration have constant treewidth. As all ingredients in the theorem are necessary, this gives the full list of obstructions to bounded treewidth in graphs that do not contain a union of $c$ cycles as an induced subgraph, and this is the first such result where the list contains some non basic obstructions (where the *basic obstructions* are complete and complete bipartite graphs, grids and their line-graphs). The result extends to graphs that do not contain the union of $c$ cycles of length at least $k$ as an induced subgraph. In a [subsequent paper](https://arxiv.org/abs/2411.11842), a subset of the authors has extended the result to graphs that do not contain the union of $c$ graphs of treewidth at least $k$ as an induced subgraph.

Localized Erdős-Pósa Property for Subdivisions

ArXiv.org · 2025-12-25

For a graph $H$, we say that $H$ has the Erdős-Pósa property for subdivisions with function $f$, if for every graph $G$, either $G$ contains (as a subgraph) $k+1$ pairwise disjoint subdivisions of $H$ or there exists a set $X\subseteq G$ such that $G\setminus X$ contains no $H$-subdivision and $|X|\leq f(k)$. We show that every $H$ that has the \EP property for subdivision also satisfies a localized version of the \EP property, as follows. Let $H$ be an $n$-vertex graph with $m\geq 1$ edges that has the Erdős-Pósa property for subdivisions with function $f$, and let $G$ be a graph that does not contain $k+1$ disjoint subdivisions of $H$. We demonstrate the existence of a set of at most $k$ vertex disjoint subdivisions of $H$ in $G$ such that in their union, we can find a set $X$ with the property that $G \setminus X$ contains no $H$-subdivision and $|X| \leq 2^{f(k)}mk +k(m-n)$.

Induced subgraphs and tree decompositions XIX. Thetas and forests

arXiv (Cornell University) · 2025-06-05

Let $H$ be a graph and let $\mathcal{C}$ be a hereditary class of theta-free graphs such that $H\notin \mathcal{C}$. We prove that if (a) $H$ is a forest; and (b) $\mathcal{C}$ excludes the line graphs of all subdivisions of some wall, then the treewidth of every graph in $\mathcal{C}$ is at most a polynomial function of its clique number. This is best possible in that both (a) and (b) are necessary for the existence of $any$ function with the above property.

Counting independent sets in structured graphs

Combinatorics Probability Computing · 2025-07-07

Abstract Counting independent sets in graphs and hypergraphs under a variety of restrictions is a classical question with a long history. It is the subject of the celebrated container method which found numerous spectacular applications over the years. We consider the question of how many independent sets we can have in a graph under structural restrictions. We show that any $n$ -vertex graph with independence number $\alpha$ without $bK_a$ as an induced subgraph has at most $n^{O(1)} \cdot \alpha ^{O(\alpha )}$ independent sets. This substantially improves the trivial upper bound of $n^{\alpha },$ whenever $\alpha \le n^{o(1)}$ and gives a characterisation of graphs forbidding which allows for such an improvement. It is also in general tight up to a constant in the exponent since there exist triangle-free graphs with $\alpha ^{\Omega (\alpha )}$ independent sets. We also prove that if one in addition assumes the ground graph is chi-bounded one can improve the bound to $n^{O(1)} \cdot 2^{O(\alpha )}$ which is tight up to a constant factor in the exponent.