From the 1 of 20 linked papers with an AI index.
20 papers
Forcing monochromatic induced subgraphs
Sepehr Hajebi, Sophie Spirkl
The paper proves that for any number of colors and a collection of nontrivial graphs, a sufficiently large edge‑colored complete graph without a monochromatic induced copy of the c…
A simple layered-wheel-like construction
Maria Chudnovsky, David Fischer, Sepehr Hajebi +2
In recent years, there has been significant interest in characterizing the induced subgraph obstructions to bounded treewidth and pathwidth. While this has recently been resolved f…
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" (th…
Suns in triangle-free graphs of large chromatic number
Sepehr Hajebi, Sophie Spirkl
For an integer , a -sun is a graph obtained from a -vertex cycle by adding a degree-one neighbor for each vertex of . Trotignon asked whether every triangle-f…