Browsing Combinatorics and Optimization by Author "Scott, Alex"
Now showing items 1-12 of 12
-
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. -
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 ... -
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 ...