Sepehr Hajebi

Cographs in chordal graphs

Sepehr Hajebi

For a graph $G$ , let $cg (G)$ be the maximum $k \in N$ for which $G$ contains a $k$ -vertex cograph as an induced subgraph. The Erdős-Hajnal conjecture asserts that for…

Forcing monochromatic induced subgraphs

Sepehr Hajebi, Sophie Spirkl

We prove that for all $c \in N$ and nonnull graphs $H_{1}, \dots, H_{t}$ , there exists $n \in N$ such that if $G$ is a $c$ -edge-colored complete graph with no monochromatic…

Asymmetric induced saturation

Xinyue Fan, Sahab Hajebi, Sepehr Hajebi +1

For which graphs $H$ does there exist a graph $G$ with at least one edge and no induced subgraph isomorphic to $H$ , such that deleting any edge of $G$ creates an induced copy of $H…

Tree-alpha and excluding finitely many graphs

Sepehr Hajebi, Sophie Spirkl

We prove that a hereditary graph class $G$ defined by finitely many excluded induced subgraphs has bounded tree- $α$ if and only if it is " $(tw, ω)$ -bounded" (that…

Polynomial bounds for pathwidth

Sepehr Hajebi

Dallard, Milanič, and Štorgel conjectured that for a hereditary graph class $G$ , if there is some function $f : N \to N$ such that every graph $G\in \mathca…

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…

Halfway to induced saturation for even cycles

Xinyue Fan, Sahab Hajebi, Sepehr Hajebi +1

For graphs $G$ and $H$ , we say that $G$ is $H$ -free if no induced subgraph of $G$ is isomorphic to $H$ , and that $G$ is $H$ -induced-saturated if $G$ is $H$ -free but removing or add…

Suns in triangle-free graphs of large chromatic number

Sepehr Hajebi, Sophie Spirkl

For an integer $t \geq 4$ , a $t$ -sun is a graph obtained from a $t$ -vertex cycle $C$ by adding a degree-one neighbor for each vertex of $C$ . Trotignon asked whether every triangle-f…

Induced subgraphs and tree decompositions XIX. Thetas and forests

Maria Chudnovsky, Julien Codsi, Sepehr Hajebi +1

Let $H$ be a graph and let $C$ be a hereditary class of theta-free graphs such that $H \in / C$ . We prove that if (a) $H$ is a forest; and (b) $C$ exc…

Bull-free graphs and $χ$ -boundedness

Sepehr Hajebi

A bull is a graph obtained from a four-vertex path by adding a vertex adjacent to the two middle vertices of the path. A graph $G$ is bull-free if no induced subgraph of $G$ is a b…

Induced subgraphs and tree decompositions XVIII. Obstructions to bounded pathwidth

Maria Chudnovsky, Sepehr Hajebi, Sophie Spirkl

The pathwidth of a graph $G$ is the smallest $w \in N$ such that $G$ can be constructed from a sequence of graphs, each on at most $w + 1$ vertices, by gluing them together i…

Induced subgraphs and tree decompositions XVII. Anticomplete sets of large treewidth

Maria Chudnovsky, Sepehr Hajebi, Sophie Spirkl

Two sets $X, Y$ of vertices in a graph $G$ are "anticomplete" if $X \cap Y = \emptyset$ and there is no edge in $G$ with an end in $X$ and an end in $Y$ . We prove that every graph $…

math.CO2024★ 1 cited

Induced subgraphs and tree decompositions XVI. Complete bipartite induced minors

Maria Chudnovsky, Sepehr Hajebi, Sophie Spirkl

We prove that for every graph $G$ with a sufficiently large complete bipartite induced minor, either $G$ has an induced minor isomorphic to a large wall, or $G$ contains a large co…

Tree Independence Number IV. Even-hole-free Graphs

Maria Chudnovsky, Peter Gartland, Sepehr Hajebi +2

We prove that the tree independence number of every even-hole-free graph is at most polylogarithmic in its number of vertices. More explicitly, we prove that there exists a constan…

Tree independence number III. Thetas, prisms and stars

Maria Chudnovsky, Sepehr Hajebi, Nicolas Trotignon

We prove that for every $t \in N$ , there exists $τ = τ (t) \in N$ such that every (theta, prism, $K_{1, t}$ )-free graph has tree independence number at most $τ$ (where…

math.CO2024★ 3 cited

Tree independence number II. Three-path-configurations

Maria Chudnovsky, Sepehr Hajebi, Daniel Lokshtanov +1

A three-path-configuration is a graph consisting of three pairwise internally-disjoint paths the union of every two of which is an induced cycle of length at least four. A graph is…