More Like this

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

   https://doi.org/10.19086/aic.2025.3  

   Alecu, Bogdan; Chudnovsky, Maria; Spirkl, Sophie (March 2025, Advances in Combinatorics)

   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. 

   more » « less
2. Maximum Spread of $$K_{s,t}$$-Minor-Free Graphs

   https://doi.org/10.37236/13410  

   Linz, William; Lu, Linyuan; Wang, Zhiyu (January 2025, The Electronic Journal of Combinatorics)

   The spread of a graph $$G$$ is the difference between the largest and smallest eigenvalue of the adjacency matrix of $$G$$. In this paper, we consider the family of graphs which contain no $$K_{s,t}$$-minor. We show that for any $$t\geq s \geq  2$$ and sufficiently large $$n$$, there is an integer $$\xi_{t}$$ such that the extremal $$n$$-vertex $$K_{s,t}$$-minor-free graph attaining the maximum spread is the graph obtained by joining a graph $$L$$ on $(s-1)$ vertices to the disjoint union of $$\lfloor \frac{2n+\xi_{t}}{3t}\rfloor$$ copies of $$K_t$$ and $$n-s+1 - t\lfloor \frac{2n+\xi_t}{3t}\rfloor$$ isolated vertices. Furthermore, we give an explicit formula for $$\xi_{t}$$ and an explicit description for the graph $$L$$ for $$t \geq \frac32(s-3) +\frac{4}{s-1}$$. 

   more » « less
3. Induced subgraphs and tree decompositions V. one neighbor in a hole

   https://doi.org/10.1002/jgt.23055  

   Abrishami, Tara; Alecu, Bogdan; Chudnovsky, Maria; Hajebi, Sepehr; Spirkl, Sophie; Vušković, Kristina (November 2023, Journal of Graph Theory)

   Abstract What are the unavoidable induced subgraphs of graphs with large treewidth? It is well‐known that the answer must include a complete graph, a complete bipartite graph, all subdivisions of a wall and line graphs of all subdivisions of a wall (we refer to these graphs as the “basic treewidth obstructions”). So it is natural to ask whether graphs excluding the basic treewidth obstructions as induced subgraphs have bounded treewidth. Sintiari and Trotignon answered this question in the negative. Their counterexamples, the so‐called “layered wheels,” contain wheels, where awheelconsists of ahole(i.e., an induced cycle of length at least four) along with a vertex with at least three neighbors in the hole. This leads one to ask whether graphs excluding wheels and the basic treewidth obstructions as induced subgraphs have bounded treewidth. This also turns out to be false due to Davies' recent example of graphs with large treewidth, no wheels and no basic treewidth obstructions as induced subgraphs. However, in Davies' example there exist holes and vertices (outside of the hole) with two neighbors in them. Here we prove that a hole with a vertex with at least two neighbors in it is inevitable in graphs with large treewidth and no basic obstruction. Our main result is that graphs in which every vertex has at most one neighbor in every hole (that does not contain it) and with the basic treewidth obstructions excluded as induced subgraphs have bounded treewidth. 

   more » « less
4. Cyclic Triangle Factors in Regular Tournaments

   https://doi.org/10.37236/7759  

   Li, Lina; Molla, Theodore (October 2019, The Electronic Journal of Combinatorics)

   Both Cuckler and Yuster independently conjectured that when $$n$$ is an odd positive multiple of $$3$$ every regular tournament on $$n$$ vertices contains a collection of $n/3$$ vertex-disjoint copies of the cyclic triangle. Soon after, Keevash \& Sudakov proved that if $$G$$ is an orientation of a graph on $$n$$ vertices in which every vertex has both indegree and outdegree at least $(1/2 - o(1))n$, then there exists a collection of vertex-disjoint cyclic triangles that covers all but at most $$3$$ vertices. In this paper, we resolve the conjecture of Cuckler and Yuster for sufficiently large $$n$$. 

   more » « less
5. On tripartite common graphs

   https://doi.org/10.1017/S0963548322000074  

   Grzesik, Andrzej; Lee, Joonkyung; Lidický, Bernard; Volec, Jan (September 2022, Combinatorics, Probability and Computing)

   Abstract A graph $$H$$ is common if the number of monochromatic copies of $$H$$ in a 2-edge-colouring of the complete graph $$K_n$$ is asymptotically minimised by the random colouring. Burr and Rosta, extending a famous conjecture of Erdős, conjectured that every graph is common. The conjectures of Erdős and of Burr and Rosta were disproved by Thomason and by Sidorenko, respectively, in the late 1980s. Collecting new examples of common graphs had not seen much progress since then, although very recently a few more graphs were verified to be common by the flag algebra method or the recent progress on Sidorenko’s conjecture. Our contribution here is to provide several new classes of tripartite common graphs. The first example is the class of so-called triangle trees, which generalises two theorems by Sidorenko and answers a question of Jagger, Šťovíček, and Thomason from 1996. We also prove that, somewhat surprisingly, given any tree $$T$$ , there exists a triangle tree such that the graph obtained by adding $$T$$ as a pendant tree is still common. Furthermore, we show that adding arbitrarily many apex vertices to any connected bipartite graph on at most $$5$$ vertices yields a common graph. 

   more » « less