S. Spirkl

activity

20132026

most citedInduced subgraphs and tree decompositions IV. (Even hole, diamond, pyramid)-free graphs

12 citations · 147 across the 77 of their papers we have counts for

collaborators

Showing 2022 · math.COShow all

14 papers · 2 filters

math.CO2022★ 10 cited

Induced subgraphs and tree-decompositions VII. Basic obstructions in $H$ -free graphs

Tara Abrishami, Bogdan Alecu, Maria Chudnovsky +2

We say a class $C$ of graphs is clean if for every positive integer $t$ there exists a positive integer $w (t)$ such that every graph in $C$ with treewidth more…

math.CO2022

Homogeneous Sets in Graphs and a Chromatic Multisymmetric Function

Logan Crew, Evan Haithcock, Josephine Reynes +1

In this paper, we extend the chromatic symmetric function $X$ to a chromatic $k$ -multisymmetric function $X_{k}$ , defined for graphs equipped with a partition of their vertex set int…

math.CO2022★ 1 cited

Induced subgraphs and tree decompositions VI. Graphs with 2-cutsets

Tara Abrishami, Maria Chudnovsky, Sepehr Hajebi +1

This paper continues a series of papers investigating the following question: which hereditary graph classes have bounded treewidth? We call a graph $t$ -clean if it does not contai…

math.CO2022★ 8 cited

Induced subgraphs and tree decompositions V. One neighbor in a hole

Tara Abrishami, Bogdan Alecu, Maria Chudnovsky +3

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 subdivisi…

math.CO2022★ 1 cited

Improved bounds for the triangle case of Aharoni's rainbow generalization of the Caccetta-Häggkvist conjecture

Patrick Hompe, Zishen Qu, Sophie Spirkl

For a digraph $G$ and $v \in V (G)$ , let $δ^{+} (v)$ be the number of out-neighbors of $v$ in $G$ . The Caccetta-Häggkvist conjecture states that for all $k \geq 1$ , if $G$ is a digraph…

math.CO2022

List-3-Coloring ordered graphs with a forbidden induced subgraph

Sepehr Hajebi, Yanjia Li, Sophie Spirkl

The List-3-Coloring Problem is to decide, given a graph $G$ and a list $L (v) \subseteq {1, 2, 3}$ of colors assigned to each vertex $v$ of $G$ , whether $G$ admits a proper coloring…

math.CO2022

Bipartite graphs with no $K_{6}$ minor

Maria Chudnovsky, Alex Scott, Paul Seymour +1

A theorem of Mader shows that every graph with average degree at least eight has a $K_{6}$ minor, and this is false if we replace eight by any smaller constant. Replacing average deg…

math.CO2022

Minimal induced subgraphs of the class of 2-connected non-Hamiltonian wheel-free graphs

Aristotelis Chaniotis, Zishen Qu, Sophie Spirkl

Given a graph $G$ and a graph property $P$ we say that $G$ is minimal with respect to $P$ if no proper induced subgraph of $G$ has the property $P$ . An HC-obstruction is a minimal…

math.CO2022★ 1 cited

Digraphs with all induced directed cycles of the same length are not $χ$ -bounded

Alvaro Carbonero, Patrick Hompe, Benjamin Moore +1

For $t \geq 2$ , let us call a digraph $D$ \emph{t-chordal} if all induced directed cycles in $D$ have length equal to $t$ . In a previous paper, we asked for which $t$ it is true tha…

math.CO2022★ 12 cited

Induced subgraphs and tree decompositions IV. (Even hole, diamond, pyramid)-free graphs

Tara Abrishami, Maria Chudnovsky, Sepehr Hajebi +1

A hole in a graph $G$ is an induced cycle of length at least four, and an even hole is a hole of even length. The diamond is the graph obtained from the complete graph $K_{4}$ by rem…

math.CO2022★ 1 cited

Pure pairs. X. Tournaments and the strong Erdos-Hajnal property

Maria Chudnovsky, Alex Scott, Paul Seymour +1

A pure pair in a tournament $G$ is an ordered pair $(A, B)$ of disjoint subsets of $V (G)$ such that every vertex in $B$ is adjacent from every vertex in $A$ . Which tournaments $H$ h…

math.CO2022★ 7 cited

Polynomial bounds for chromatic number VI. Adding a four-vertex path

Maria Chudnovsky, Alex Scott, Paul Seymour +1

A class of graphs is $χ$ -bounded if there is a function $f$ such that every graph $G$ in the class has chromatic number at most $f (ω (G))$ , where $ω (G)$ is the clique number of $G$ ;…

math.CO2022★ 1 cited

A counterexample to a conjecture about triangle-free induced subgraphs of graphs with large chromatic number

Alvaro Carbonero, Patrick Hompe, Benjamin Moore +1

We prove that for every $n$ , there is a graph $G$ with $χ (G) \geq n$ and $ω (G) \leq 3$ such that every induced subgraph $H$ of $G$ with $ω (H) \leq 2$ satisfies $χ (H) \leq 4$ . This…

math.CO2022

Pure pairs. VIII. Excluding a sparse graph

Alex Scott, Paul Seymour, Sophie Spirkl

A pure pair of size $t$ in a graph $G$ is a pair $A, B$ of disjoint sets of $t$ vertices such that $A$ is either complete or anticomplete to $B$ . It is known that, for every forest…

Induced subgraphs and tree-decompositions VII. Basic obstructions in H-free graphs

Homogeneous Sets in Graphs and a Chromatic Multisymmetric Function

Induced subgraphs and tree decompositions VI. Graphs with 2-cutsets

Induced subgraphs and tree decompositions V. One neighbor in a hole

Improved bounds for the triangle case of Aharoni's rainbow generalization of the Caccetta-Häggkvist conjecture

List-3-Coloring ordered graphs with a forbidden induced subgraph

Bipartite graphs with no K6​ minor

Minimal induced subgraphs of the class of 2-connected non-Hamiltonian wheel-free graphs

Digraphs with all induced directed cycles of the same length are not χ​-bounded

Induced subgraphs and tree decompositions IV. (Even hole, diamond, pyramid)-free graphs

Pure pairs. X. Tournaments and the strong Erdos-Hajnal property

Polynomial bounds for chromatic number VI. Adding a four-vertex path

A counterexample to a conjecture about triangle-free induced subgraphs of graphs with large chromatic number

Pure pairs. VIII. Excluding a sparse graph

Induced subgraphs and tree-decompositions VII. Basic obstructions in $H$ -free graphs

Bipartite graphs with no $K_{6}$ minor

Digraphs with all induced directed cycles of the same length are not $χ$ -bounded