Sophie Spirkl

collaborators

7 papers

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

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.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.CO2025

The structure of $I^ (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 $I^ (1, 2, 2)$ be a…

math.CO2025

Intersections of graphs and $I ¨ $ -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…

Crossing tournaments are polynomially χ​-bounded

Decomposing tournaments into comparability graphs

Faster 3-colouring algorithm for graphs of diameter 3

Characterizing Large Clique Number in Tournaments

The structure of I^(1,2,2)-free tournaments

Intersections of graphs and I¨-boundedness

Crossing tournaments are polynomially $χ$ -bounded

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

Intersections of graphs and $I ¨ $ -boundedness