12 citations · 147 across the 77 of their papers we have counts for
7 papers · 2 filters
Almost perfect graph classes
Cicely Henderson, Hidde Koerts, Taite LaGrange +4
A graph is perfect if for each induced subgraph of . In 2002, Chudnovsky, Robertson, Seymour, and Thomas famously proved the Strong Perfect Graph Theorem.…
Forcing monochromatic induced subgraphs
Sepehr Hajebi, Sophie Spirkl
We prove that for all and nonnull graphs , there exists such that if is a -edge-colored complete graph with no monochromatic…
Asymmetric induced saturation
Xinyue Fan, Sahab Hajebi, Sepehr Hajebi +1
For which graphs does there exist a graph with at least one edge and no induced subgraph isomorphic to , such that deleting any edge of creates an induced copy of $H…
The Twin-Width of Graphs of Bounded VC-Dimension
Therese Biedl, Taite LaGrange, Sophie Spirkl
In this paper, we investigate which hereditary classes of graphs admit sub-linear (in the number of vertices) bounds on twin-width. By modifying conference graphs, we can show that…
Tree-alpha and excluding finitely many graphs
Sepehr Hajebi, Sophie Spirkl
We prove that a hereditary graph class defined by finitely many excluded induced subgraphs has bounded tree- if and only if it is "-bounded" (that…
A positive instance of Scott's Conjecture on induced subdivisions
Kathie Cameron, Ni Luh Dewi Sintiari, Sophie Spirkl
For a graph , denotes the chromatic number of and denotes the size of the largest clique in . A hereditary class of graphs is called -bounded if there is…
Complexity of the Feedback Vertex Set Problem in Tournaments with Forbidden Subtournaments
Sophie Spirkl, Yun Xing
In this paper, we consider the complexity of the minimum feedback vertex set problem (MFBVS) for tournaments with forbidden subtournaments. The MFBVS problem in general tournaments…