More Like this

1. Excluding disjoint Kuratowski graphs

   https://doi.org/10.1016/j.jctb.2026.01.002  

   Robertson, Neil; Seymour, Paul (May 2026, Journal of Combinatorial Theory, Series B)

   A graph is a k-Kuratowski graph if it has exactly k components, each isomorphic to K5 or to K3,3. We prove that if a graph G contains no k-Kuratowski graph as a minor, then there is a set X of boundedly many vertices such that G∖X can be drawn in a (possibly disconnected) surface in which no k-Kuratowski graph can be drawn. 

   more » « less
2. Induced Subgraph Density. I. A loglog Step Towards Erd̋s–Hajnal

   https://doi.org/10.1093/imrn/rnae065  

   Bucić, Matija; Nguyen, Tung; Scott, Alex; Seymour, Paul (May 2024, International Mathematics Research Notices)

   Abstract In 1977, Erd̋s and Hajnal made the conjecture that, for every graph $$H$$, there exists $c>0$ such that every $$H$$-free graph $$G$$ has a clique or stable set of size at least $$|G|^{c}$$, and they proved that this is true with $$ |G|^{c}$$ replaced by $$2^{c\sqrt{\log |G|}}$$. Until now, there has been no improvement on this result (for general $$H$$). We prove a strengthening: that for every graph $$H$$, there exists $c>0$ such that every $$H$$-free graph $$G$$ with $$|G|\ge 2$$ has a clique or stable set of size at least $$ \begin{align*} &2^{c\sqrt{\log |G|\log\log|G|}}.\end{align*} $$ Indeed, we prove the corresponding strengthening of a theorem of Fox and Sudakov, which in turn was a common strengthening of theorems of Rödl, Nikiforov, and the theorem of Erd̋s and Hajnal mentioned above. 

   more » « less
3. Pure Pairs. V. Excluding Some Long Subdivision

   https://doi.org/10.1007/s00493-023-00025-8  

   Scott, Alex; Seymour, Paul; Spirkl, Sophie (June 2023, Combinatorica)

   A “pure pair” in a graph G is a pair A, B of disjoint subsets of V(G) such that A is complete or anticomplete to B. Jacob Fox showed that for all ε>0, there is a comparability graph G with n vertices, where n is large, in which there is no pure pair A, B with |A|,|B|≥εn. He also proved that for all c>0 there exists ε>0 such that for every comparability graph G with n>1 vertices, there is a pure pair A, B with |A|,|B|≥εn1−c; and conjectured that the same holds for every perfect graph G. We prove this conjecture and strengthen it in several ways. In particular, we show that for all c>0, and all ℓ1,ℓ2≥4/c+9, there exists ε>0 such that, if G is an (n>1)-vertex graph with no hole of length exactly ℓ1 and no antihole of length exactly ℓ2, then there is a pure pair A, B in G with |A|≥εn and |B|≥εn1−c. This is further strengthened, replacing excluding a hole by excluding some “long” subdivision of a general graph. 

   more » « less
4. Hyperbolic families and coloring graphs on surfaces

   https://doi.org/https://doi.org/10.1090/btran/26  

   Postle, Luke; Thomas, Robin (December 2018, Transactions of the American Mathematical Society. Series B)

   We develop a theory of linear isoperimetric inequalities for graphs on surfaces and apply it to coloring problems, as follows. Let $ G$ be a graph embedded in a fixed surface $$ \Sigma $$ of genus $ g$ and let $$ L=(L(v):v\in V(G))$$ be a collection of lists such that either each list has size at least five, or each list has size at least four and $ G$ is triangle-free, or each list has size at least three and $ G$ has no cycle of length four or less. An $ L$-coloring of $ G$ is a mapping $$ \phi $$ with domain $ V(G)$ such that $$ \phi (v)\in L(v)$$ for every $$ v\in V(G)$$ and $$ \phi (v)\ne \phi (u)$$ for every pair of adjacent vertices $$ u,v\in V(G)$$. We prove if every non-null-homotopic cycle in $ G$ has length $$ \Omega (\log g)$$, then $ G$ has an $ L$-coloring, if $ G$ does not have an $ L$-coloring, but every proper subgraph does (``$ L$-critical graph''), then $$ \vert V(G)\vert=O(g)$$, if every non-null-homotopic cycle in $ G$ has length $$ \Omega (g)$$, and a set $$ X\subseteq V(G)$$ of vertices that are pairwise at distance $$ \Omega (1)$$ is precolored from the corresponding lists, then the precoloring extends to an $ L$-coloring of $ G$, if every non-null-homotopic cycle in $ G$ has length $$ \Omega (g)$$, and the graph $ G$ is allowed to have crossings, but every two crossings are at distance $$ \Omega (1)$$, then $ G$ has an $ L$-coloring, if $ G$ has at least one $ L$-coloring, then it has at least $$ 2^{\Omega (\vert V(G)\vert)}$$ distinct $ L$-colorings. We show that the above assertions are consequences of certain isoperimetric inequalities satisfied by $ L$-critical graphs, and we study the structure of families of embedded graphs that satisfy those inequalities. It follows that the above assertions hold for other coloring problems, as long as the corresponding critical graphs satisfy the same inequalities. 

   more » « less
5. Leibniz International Proceedings in Informatics (LIPIcs):36th International Symposium on Computational Geometry (SoCG 2020)

   https://doi.org/10.4230/LIPIcs.SoCG.2020.6  

   Ameer, Safwa; Gibson-Lopez, Matt; Krohn, Erik; Soderman, Sean; Wang, Qing (June 2020, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Cabello, Sergio; Chen, Danny Z. (Ed.)

   In this paper, we consider the Visibility Graph Recognition and Reconstruction problems in the context of terrains. Here, we are given a graph G with labeled vertices v₀, v₁, …, v_{n-1} such that the labeling corresponds with a Hamiltonian path H. G also may contain other edges. We are interested in determining if there is a terrain T with vertices p₀, p₁, …, p_{n-1} such that G is the visibility graph of T and the boundary of T corresponds with H. G is said to be persistent if and only if it satisfies the so-called X-property and Bar-property. It is known that every "pseudo-terrain" has a persistent visibility graph and that every persistent graph is the visibility graph for some pseudo-terrain. The connection is not as clear for (geometric) terrains. It is known that the visibility graph of any terrain T is persistent, but it has been unclear whether every persistent graph G has a terrain T such that G is the visibility graph of T. There actually have been several papers that claim this to be the case (although no formal proof has ever been published), and recent works made steps towards building a terrain reconstruction algorithm for any persistent graph. In this paper, we show that there exists a persistent graph G that is not the visibility graph for any terrain T. This means persistence is not enough by itself to characterize the visibility graphs of terrains, and implies that pseudo-terrains are not stretchable. 

   more » « less