S. Spirkl

Almost perfect graph classes

Cicely Henderson, Hidde Koerts, Taite LaGrange +4

A graph $G$ is perfect if $ω (H) = χ (H)$ for each induced subgraph $H$ of $G$ . 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 $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…

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 $G$ defined by finitely many excluded induced subgraphs has bounded tree- $α$ if and only if it is " $(tw, ω)$ -bounded" (that…

A positive instance of Scott's Conjecture on induced subdivisions

Kathie Cameron, Ni Luh Dewi Sintiari, Sophie Spirkl

For a graph $G$ , $χ (G)$ denotes the chromatic number of $G$ and $ω (G)$ denotes the size of the largest clique in $G$ . 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…

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…

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…

math.CO2024★ 1 cited

Maximum $k$ -colourable induced subgraphs in $(P_{5} + r K_{1})$ -free graphs

Cicely Henderson, Evelyne Smith-Roberge, Sophie Spirkl +1

We show that for any nonnegative integer $r$ , the Weighted Maximum List- $k$ -Colourable Induced Subgraph problem can be solved in polynomial time for input graphs that do not contai…

Orientations of graphs with at most one directed path between every pair of vertices

Barbora Dohnalová, Jiří Kalvoda, Gaurav Kucheriya +1

Given a graph $G$ , we say that an orientation $D$ of $G$ is a KT orientation if, for all $u, v \in V (D)$ , there is at most one directed path (in any direction) between $u$ and $v$ .…

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…

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…

The sandwich problem for odd-hole-free and even-hole-free graphs

Kathie Cameron, Aristotelis Chaniotis, Celina M. H. de Figueiredo +1

For a property $P$ of graphs, the $P$ -\textsc{Sandwich-Problem}, introduced by Golumbic and Shamir (1993), is the following: Given a pair of graphs $(G_{1}, G_{2})$ …

Graphs of bounded chordality

Aristotelis Chaniotis, Babak Miraftab, Sophie Spirkl

A hole in a graph is an induced subgraph which is a cycle of length at least four. A graph is chordal if it contains no holes. Following McKee and Scheinerman (1993), we define the…

Induced subgraphs and tree decompositions XV. Even-hole-free graphs with bounded clique number have logarithmic treewidth

Maria Chudnovsky, Peter Gartland, Sepehr Hajebi +2

We prove that for every integer $t \geq 1$ there exists an integer $c_{t} \geq 1$ such that every $n$ -vertex even-hole-free graph with no clique of size $t$ has treewidth at most $c_t\…