3 citations · 4 across the 12 of their papers we have counts for
11 papers · 1 filter
Almost perfect graph classes
Cicely Henderson, Hidde Koerts, Taite LaGrange +4
A graph is perfect if for each induced subgraph of . In 2002, Chudnovsky, Robertson, Seymour, and Thomas famously proved the Strong Perfect Graph Theorem.…
Crossing tournaments are polynomially -bounded
Lila Crew, Xinyue Fan, Hidde Koerts +2
Given a tournament , Aboulker, Aubian, Charbit, and Lopes (2023) defined its clique number as the minimum clique number of a backedge graph of , and raised the que…
Tree-independence number of -free graph classes
Kenny Bešter Štorgel, Mujin Choi, Hidde Koerts +1
In this paper, we investigate the tree-independence number of graph classes that do not contain as an induced subgraph. Dallard et al. conjectured that for any positive i…
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 , denoted , defined as the minimum integer such that $A(D)=A(P_1)\cup\cdots\cup…
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 is a t…
Faster 3-colouring algorithm for graphs of diameter 3
Carla Groenland, Hidde Koerts, Sophie Spirkl
We show that given an -vertex graph of diameter 3 we can decide if is -colourable in time for any . This improves on…
Intersections of graphs and -boundedness
Aristotelis Chaniotis, Hidde Koerts, Sophie Spirkl
Given graphs , their intersection is the graph . Given graph classes $\mathcal{G}_{1}, \ldots , \m…
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 for which for every fixed there exists a constant such that every digraph without loops or parallel…
On the pre- and post-positional semi-random graph processes
Pu Gao, Hidde Koerts
We study the semi-random graph process, and a variant process recently suggested by Nick Wormald. We show that these two processes are asymptotically equally fast in constructing a…
On heroes in digraphs with forbidden induced forests
Alvaro Carbonero, Hidde Koerts, Benjamin Moore +1
We continue a line of research which studies which hereditary families of digraphs have bounded dichromatic number. For a class of digraphs , a hero in i…
On the -independence number of graph products
Aida Abiad, Hidde Koerts
The -independence number of a graph, , is the maximum size of a set of vertices at pairwise distance greater than , or alternatively, the independence number of the $…