Search for: All records

Let 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 F is the set of vertices of a subtree of T? It is necessary that F has the Helly property and the intersection graph of 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 F. 

We prove that for every graph G with a sufficiently large complete bipartite induced minor, either G has an induced minor isomorphic to a large wall, or G contains a large constellation; that is, a complete bipartite induced minor model such that on one side of the bipartition, each branch set is a singleton, and on the other side, each branch set induces a path. We further refine this theorem by characterizing the unavoidable induced subgraphs of large constellations as two types of highly structured constellations. These results will be key ingredients in several forthcoming papers of this series. 

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. 

Let G be a Berge graph that has no odd prism and no antihole of length at least six as an induced subgraph. We show that every such graph G with no balanced skew-partition is either complete or has an even pair. 

The celebrated Erdős-Pósa Theorem, in one formulation, asserts that for every c ∈ N, graphs with no subgraph (or equivalently, minor) isomorphic to the disjoint union of c cycles have bounded treewidth. What can we say about the treewidth of graphs containing no induced subgraph isomorphic to the disjoint union of c cycles? Let us call these graphs c-perforated. While 1-perforated graphs have treewidth one, complete graphs and complete bipartite graphs are examples of 2-perforated graphs with arbitrarily large treewidth. But there are sparse examples, too: Bonamy, Bonnet, Déprés, Esperet, Geniet, Hilaire, Thomassé and Wesolek constructed 2-perforated graphs with arbitrarily large treewidth and no induced subgraph isomorphic to K3 or K3,3; we call these graphs occultations. Indeed, it turns out that a mild (and inevitable) adjustment of occultations provides examples of 2-perforated graphs with arbitrarily large treewidth and arbitrarily large girth, which we refer to as full occultations. Our main result shows that the converse also holds: for every c ∈ N, a c-perforated graph has large treewidth if and only if it contains, as an induced subgraph, either a large complete graph, or a large complete bipartite graph, or a large full occultation. This distinguishes c-perforated graphs, among graph classes purely defined by forbidden induced subgraphs, as the first to admit a grid-type theorem incorporating obstructions other than subdivided walls and their line graphs. More generally, for all c, o ∈ N, we establish a full characterization of induced subgraph obstructions to bounded treewidth in graphs containing no induced subgraph isomorphic to the disjoint union of c cycles, each of length at least o + 2. 

We construct classes of graphs that are variants of the so-calledlayered wheel. One of their key properties is that while the treewidth is bounded by a function of the clique number, the construction can be adjusted to make the dependence grow arbitrarily. Some of these classes provide counter-examples to several conjectures. In particular, the construction includes hereditary classes of graphs whose treewidth is bounded by a function of the clique number while the tree-independence number is unbounded, thus disproving a conjecture of Dallard, Milanič and Štorgel [Treewidth versus clique number. II. Tree-independence number.Journal of Combinatorial Theory, Series B, 164:404–442, 2024]. The construction can be further adjusted to provide, for any fixed integer $c$ , graphs of arbitrarily large treewidth that contain no $K_c$ -free graphs of high treewidth, thus disproving a conjecture of Hajebi [Chordal graphs, even-hole-free graphs and sparse obstructions to bounded treewidth, arXiv:2401.01299, 2024]. 

A clock is a graph consisting of an induced cycle and a vertex not in with at least two non-adjacent neighbours in . We show that every clock-free graph of large treewidth contains a “basic obstruction” of large treewidth as an induced subgraph: a complete graph, a subdivision of a wall, or the line graph of a subdivision of a wall. 

A string graph is the intersection graph of curves in the plane. Kratochvíl previously showed the existence of infinitely many obstacles: graphs that are not string graphs but for which any edge contraction or vertex deletion produces a string graph. Kratochvíl’s obstacles contain arbitrarily large cliques, so they have girth three and unbounded degree. We extend this line of working by studying obstacles among graphs of restricted girth and/or degree. We construct an infinite family of obstacles of girth four; in addition, our construction is K_{2,3}-subgraph-free and near-planar (planar plus one edge). Furthermore, we prove that there is a subcubic obstacle of girth three, and that there are no subcubic obstacles of high girth. We characterize the subcubic string graphs as having a matching whose contraction yields a planar graph, and based on this characterization we find a linear-time algorithm for recognizing subcubic string graphs of bounded treewidth. 

We give a combinatorial polynomial-time algorithm to find a maximum weight independent set in perfect graphs of bounded degree that do not contain a prism or a hole of length four as an induced subgraph. An even pair in a graph is a pair of vertices all induced paths between which are even. An even set is a set of vertices every two of which are an even pair. We show that every perfect graph that does not contain a prism or a hole of length four as an induced subgraph has a balanced separator which is the union of a bounded number of even sets, where the bound depends only on the maximum degree of the graph. This allows us to solve the maximum weight independent set problem using the well-known submodular function minimization algorithm. Funding: This work was supported by the Engineering and Physical Sciences Research Council [Grant EP/V002813/1]; the National Science Foundation [Grants DMS-1763817, DMS-2120644, and DMS-2303251]; and Alexander von Humboldt-Stiftung. 

Given c ∈ N, we say a graph G is c-pinched if G does not contain an induced subgraph consisting of c cycles, all going through a single common vertex and otherwise pairwise disjoint and with no edges between them. What can be said about the structure of c-pinched graphs? For instance, 1-pinched graphs are exactly graphs of treewidth 1. However, bounded treewidth for c > 1 is immediately seen to be a false hope because complete graphs, complete bipartite graphs, subdivided walls and line graphs of subdivided walls are all examples of 2-pinched graphs with arbitrarily large treewidth. There is even a fifth obstruction for larger values of c, discovered by Pohoata and later independently by Davies, consisting of 3-pinched graphs with unbounded treewidth and no large induced subgraph isomorphic to any of the first four obstructions. We fuse the above five examples into a grid-type theorem fully describing the unavoidable induced subgraphs of pinched graphs with large treewidth. More precisely, we prove that for every c ∈ N, a c-pinched graph G has large treewidth if and only if G contains one of the following as an induced subgraph: a large complete graph, a large complete bipartite graph, a subdivision of a large wall, the line graph of a subdivision of a large wall, or a large graph from the Pohoata-Davies construction. Our main result also generalizes to an extension of pinched graphs where the lengths of excluded cycles are lower-bounded.