Sophie Spirkl

collaborators

Showing math.COShow all

7 papers · 1 filter

math.CO2026

Crossing tournaments are polynomially $χ$ -bounded

Lila Crew, Xinyue Fan, Hidde Koerts +2

Given a tournament $T$ , Aboulker, Aubian, Charbit, and Lopes (2023) defined its clique number $ω (T)$ as the minimum clique number of a backedge graph of $T$ , and raised the que…

math.CO2026

Decomposing tournaments into comparability graphs

Pierre Aboulker, Logan Crew, Julien Duron +7

In this note, we introduce the \emph{partial order decomposition number} of a digraph $D$ , denoted $p o d (D)$ , defined as the minimum integer $k$ such that $A(D)=A(P_1)\cup\cdots\cup…

math.CO2026

Characterizing Large Clique Number in Tournaments

Logan Crew, Xinyue Fan, Hidde Koerts +2

Aboulker, Aubian, Charbit, and Lopes (2023) defined the clique number of a tournament to be the minimum clique number of one of its backedge graphs. Here we show that if $T$ is a t…

math.CO2026

Faster 3-colouring algorithm for graphs of diameter 3

Carla Groenland, Hidde Koerts, Sophie Spirkl

We show that given an $n$ -vertex graph $G$ of diameter 3 we can decide if $G$ is $3$ -colourable in time $2^{O (n^{2/3 - ε})}$ for any $ε < 1/33$ . This improves on…

math.CO2025

The structure of $Δ (1, 2, 2)$ -free tournaments

Seokbeom Kim, Taite LaGrange, Mathieu Rundström +2

We extend the list of tournaments $S$ for which the complete structural description for tournaments excluding $S$ as a subtournament is known. Specifically, let $Δ (1, 2, 2)$ be a t…

math.CO2025

Intersections of graphs and $χ$ -boundedness

Aristotelis Chaniotis, Hidde Koerts, Sophie Spirkl

Given $k$ graphs $G_{1}, \dots, G_{k}$ , their intersection is the graph $(\cap_{i \in [k]} V (G_{i}), \cap_{i \in [k]} E (G_{i}))$ . Given $k$ graph classes $\mathcal{G}_{1}, \ldots , \m…

math.CO2025

Orientations of cycles in digraphs of high chromatic number and high minimum out-degree

Hidde Koerts, Benjamin Moore, Sophie Spirkl

We characterize all orientations of cycles $C$ for which for every fixed $ε > 0$ there exists a constant $c \geq 1$ such that every digraph $D$ without loops or parallel…

Crossing tournaments are polynomially χ​-bounded

Decomposing tournaments into comparability graphs

Characterizing Large Clique Number in Tournaments

Faster 3-colouring algorithm for graphs of diameter 3

The structure of Δ(1,2,2)-free tournaments

Intersections of graphs and χ-boundedness

Orientations of cycles in digraphs of high chromatic number and high minimum out-degree

Crossing tournaments are polynomially $χ$ -bounded

The structure of $Δ (1, 2, 2)$ -free tournaments

Intersections of graphs and $χ$ -boundedness