Browsing Combinatorics and Optimization by Author "Seymour, Paul"
Now showing items 1-18 of 18
-
Caterpillars in Erdős–Hajnal
Liebenau, Anita; Pilipczuk, Marcin; Seymour, Paul; Spirkl, Sophie (Elsevier, 2019-05)Let T be a tree such that all its vertices of degree more than two lie on one path; that is, T is a caterpillar subdivision. We prove that there exists ε > 0 such that for every graph G with |V(G)| ≥ 2 not containing T as ... -
Colouring perfect graphs with bounded clique number
Chudnovsky, Maria; Lagoutte, Aurélie; Seymour, Paul; Spirkl, Sophie (Elsevier, 2017-01)A graph is perfect if the chromatic number of every induced subgraph equals the size of its largest clique, and an algorithm of Grötschel, Lovász, and Schrijver [9] from 1988 finds an optimal colouring of a perfect graph ... -
Concatenating Bipartite Graphs
Chudnovsky, Maria; Hompe, Patrick; Scott, Alex; Seymour, Paul; Spirkl, Sophie (The Electronic Journal of Combinatorics, 2022)Let x, y E (0, 1], and let A, B, C be disjoint nonempty stable subsets of a graph G, where every vertex in A has at least x |B| neighbors in B, and every vertex in B has at least y|C| neighbors in C, and there are no edges ... -
Detecting an Odd Hole
Chudnovsky, Maria; Scott, Alex; Seymour, Paul; Spirkl, Sophie (Association for Computing Machinery, 2020-02)We give a polynomial-time algorithm to test whether a graph contains an induced cycle with length more than three and odd. -
Even pairs and prism corners in square-free Berge graphs
Chudnovsky, Maria; Maffray, Frédéric; Seymour, Paul; Spirkl, Sophie (Elsevier, 2018-07)Let G be a Berge graph such that no induced subgraph is a 4-cycle or a line-graph of a bipartite subdivision of K4. We show that every such graph G either is a complete graph or has an even pair. -
Finding an induced path that is not a shortest path
Berger, Eli; Seymour, Paul; Spirkl, Sophie (Elsevier, 2021-07)We give a polynomial-time algorithm that, with input a graph G and two vertices u; v of G, decides whether there is an induced uv-path that is longer than the shortest uv-path. -
H-colouring Pt-free graphs in subexponential time
Groenland, Carla; Okrasa, Karolina; Rzążewski, Paweł; Scott, Alex; Seymour, Paul; Spirkl, Sophie (Elsevier, 2019-08-31)A graph is called Pt-free if it does not contain the path on t vertices as an induced subgraph. Let H be a multigraph with the property that any two distinct vertices share at most one common neighbour. We show that the ... -
Induced subgraphs of graphs with large chromatic number. VIII. Long odd holes
Chudnovsky, Maria; Scott, Alex; Seymour, Paul; Spirkl, Sophie (Elsevier, 2020-01)We prove a conjecture of András Gyárfás, that for all k, l, every graph with clique number at most κ and sufficiently large chromatic number has an odd hole of length at least ℓ. -
A note on simplicial cliques
Chudnovsky, Maria; Scott, Alex; Seymour, Paul; Spirkl, Sophie (Elsevier, 2021-09)Motivated by an application in condensed matter physics and quantum information theory, we prove that every non-null even-hole-free claw-free graph has a simplicial clique, that is, a clique K such that for every vertex v ... -
Polynomial bounds for chromatic number II: Excluding a star-forest
Scott, Alex; Seymour, Paul; Spirkl, Sophie (Wiley, 2022-10)The Gyárfás–Sumner conjecture says that for every forest H, there is a function fH such that if G is H-free then x(G) ≤ fH(w(G)) (where x,w are the chromatic number and the clique number of G). Louis Esperet conjectured ... -
Polynomial bounds for chromatic number. III. Excluding a double star
Scott, Alex; Seymour, Paul; Spirkl, Sophie (Wiley, 2022-10)A “double star” is a tree with two internal vertices. It is known that the Gyárfás-Sumner conjecture holds for double stars, that is, for every double star H, there is a function fH such that if G does not contain H as ... -
Proof of the Kalai-Meshulam conjecture
Chudnovsky, Maria; Scott, Alex; Seymour, Paul; Spirkl, Sophie (Springer Nature, 2020-07-01)Let G be a graph, and let fG be the sum of (−1)∣A∣, over all stable sets A. If G is a cycle with length divisible by three, then fG = ±2. Motivated by topological considerations, G. Kalai and R. Meshulam [8] made the ... -
Pure pairs. I. Trees and linear anticomplete pairs
Chudnovsky, Maria; Scott, Alex; Seymour, Paul; Spirkl, Sophie (Elsevier, 2020-12-02)The Erdős-Hajnal conjecture asserts that for every graph H there is a constant c > 0 such that every graph G that does not contain H as an induced subgraph has a clique or stable set of cardinality at least |G|c. In this ... -
Pure pairs. II. Excluding all subdivisions of a graph
Chudnovsky, Maria; Scott, Alex; Seymour, Paul; Spirkl, Sophie (Springer Nature, 2021-06-01)We prove for every graph H there exists ɛ > 0 such that, for every graph G with |G|≥2, if no induced subgraph of G is a subdivision of H, then either some vertex of G has at least ɛ|G| neighbours, or there are two disjoint ... -
Pure pairs. III. Sparse graphs with no polynomial-sized anticomplete pairs
Chudnovsky, Maria; Fox, Jacob; Scott, Alex; Seymour, Paul; Spirkl, Sophie (Wiley, 2020-11)A graph is H-free if it has no induced subgraph isomorphic to H, and |G| denotes the number of vertices of G. A conjecture of Conlon, Sudakov and the second author asserts that: - For every graph H, there exists ∈ > 0 ... -
Short Directed Cycles in Bipartite Digraphs
Seymour, Paul; Spirkl, Sophie (Springer Nature, 2020-08-01)The Caccetta-Häggkvist conjecture implies that for every integer k ≥ 1, if G is a bipartite digraph, with n vertices in each part, and every vertex has out-degree more than n/(k+1), then G has a directed cycle of length ... -
Towards Erdős-Hajnal for Graphs with No 5-Hole
Chudnovsky, Maria; Fox, Jacob; Scott, Alex; Seymour, Paul; Spirkl, Sophie (Springer Nature, 2019-11-01)The Erdős-Hajnal conjecture says that for every graph H there exists c > 0 such that max(α(G), w(G)) ≥ nc for every H-free graph G with n vertices, and this is still open when H = C5. Until now the best bound known on ... -
Triangle-free graphs with no six-vertex induced path
Chudnovsky, Maria; Seymour, Paul; Spirkl, Sophie; Zhong, Mingxian (Elsevier, 2018-08)The graphs with no five-vertex induced path are still not understood. But in the triangle-free case, we can do this and one better; we give an explicit construction for all triangle-free graphs with no six-vertex induced ...