12 citations · 147 across the 77 of their papers we have counts for
17 papers · 2 filters
The -coloring and maximum stable set problem in hypergraphs with bounded matching number and edge size
Yanjia Li, Sophie Spirkl
Motivated by the analogous questions in graphs, we study the complexity of coloring and stable set problems in hypergraphs with forbidden substructures and bounded edge size. Letti…
Pure pairs. IX. Transversal trees
Alex Scott, Paul Seymour, Sophie Spirkl
Fix k>0, and let G be a graph, with vertex set partitioned into k subsets (`blocks') of approximately equal size. An induced subgraph of G is transversal (with respect to this part…
Polynomial bounds for chromatic number. IV. A near-polynomial bound for excluding the five-vertex path
Alex Scott, Paul Seymour, Sophie Spirkl
A graph G is H-free if it has no induced subgraph isomorphic to H. We prove that a -free graph with clique number has chromatic number at most . The be…
Induced subgraphs and tree decompositions III. Three-path-configurations and logarithmic treewidth
Tara Abrishami, Maria Chudnovsky, Sepehr Hajebi +1
A theta is a graph consisting of two non-adjacent vertices and three internally disjoint paths between them, each of length at least two. For a family of graphs, we s…
Polynomial bounds for chromatic number. III. Excluding a double star
Alex Scott, Paul Seymour, Sophie Spirkl
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 , there is a function $…
Minimal induced subgraphs of two classes of 2-connected non-Hamiltonian graphs
Joseph Cheriyan, Sepehr Hajebi, Zishen Qu +1
In 1981, Duffus, Gould, and Jacobson showed that every connected graph either has a Hamiltonian path, or contains a claw () or a net (a fixed six-vertex graph) as an induc…
Plethysms of Chromatic and Tutte Symmetric Functions
Logan Crew, Sophie Spirkl
Plethysm is a fundamental operation in symmetric function theory, derived directly from its connection with representation theory. However, it does not admit a simple combinatorial…
Induced subgraphs and tree decompositions II. Toward walls and their line graphs in graphs of bounded degree
Tara Abrishami, Maria Chudnovsky, Cemil Dibek +4
This paper is motivated by the following question: what are the unavoidable induced subgraphs of graphs with large treewidth? Aboulker et al. made a conjecture which answers this q…
Polynomial bounds for chromatic number. II. Excluding a star-forest
Alex Scott, Paul Seymour, Sophie Spirkl
The Gyarfas-Sumner conjecture says that for every forest , there is a function such that if is -free then (where are the chromatic number and…
Pure pairs. V. Excluding some long subdivision
Alex Scott, Paul Seymour, Sophie Spirkl
A pure pair in a graph is a pair of disjoint subsets of such that is complete or anticomplete to . Jacob Fox showed that for all , there is a comparabi…
Further approximations for Aharoni's rainbow generalization of the Caccetta-Häggkvist conjecture
Patrick Hompe, Sophie Spirkl
For a digraph and , let be the number of out-neighbors of in . The Caccetta-Häggkvist conjecture states that for all , if is a digraph…
Complexity dichotomy for List-5-Coloring with a forbidden induced subgraph
Sepehr Hajebi, Yanjia Li, Sophie Spirkl
For a positive integer and graphs and , we denote by the disjoint union of and , and by the union of mutually disjoint copies of . Also, we say…
Polynomial bounds for chromatic number. I. Excluding a biclique and an induced tree
Alex Scott, Paul Seymour, Sophie Spirkl
Let H be a tree. It was proved by Rodl that graphs that do not contain H as an induced subgraph, and do not contain the complete bipartite graph as a subgraph, have bound…
Modular Relations of the Tutte Symmetric Function
Logan Crew, Sophie Spirkl
For a graph , its Tutte symmetric function generalizes both the Tutte polynomial and the chromatic symmetric function . We may also consider as a map from…
Erdos-Hajnal for graphs with no 5-hole
Maria Chudnovsky, Alex Scott, Paul Seymour +1
The Erdos-Hajnal conjecture says that for every graph H there exists c>0 such that every graph G not containing H as an induced subgraph has a clique or stable set of cardinality a…
Pure pairs. VII. Homogeneous submatrices in 0/1-matrices with a forbidden submatrix
Alex Scott, Paul Seymour, Sophie Spirkl
For integer , let be the number of rows of the largest all-0 or all-1 square submatrix of , minimized over all -matrices . Thus …
On Aharoni's rainbow generalization of the Caccetta-Häggkvist conjecture
Patrick Hompe, Petra Pelikanova, Aneta Pokorna +1
For a digraph and , let be the number of out-neighbors of in . The Caccetta-Häggkvist conjecture states that for all , if is a digraph…