research
∙
04/10/2023
Digraph Colouring and Arc-Connectivity
The dichromatic number χ⃗(D) of a digraph D is the minimum size of a par...
share
research
∙
12/05/2022
(P6, triangle)-free digraphs have bounded dichromatic number
The dichromatic number of an oriented graph is the minimum size of a par...
research
∙
08/03/2022
Various bounds on the minimum number of arcs in a k-dicritical digraph
The dichromatic number χ⃗(G) of a digraph G is the least integer k such ...
research
∙
07/03/2022
On the minimum number of arcs in k-dicritical oriented graphs
The dichromatic number (D) of a digraph D is the least integer k such th...
research
∙
02/27/2022
Heroes in oriented complete multipartite graphs
The dichromatic number of a digraph is the minimum size of a partition o...
research
∙
02/18/2022
Heroes in orientations of chordal graphs
We characterize all digraphs H such that orientations of chordal graphs ...
research
∙
01/27/2022
Vizing's and Shannon's Theorems for defective edge colouring
We call a multigraph (k,d)-edge colourable if its edge set can be partit...
research
∙
09/03/2021
Four proofs of the directed Brooks' Theorem
We give four new proofs of the directed version of Brook's Theorem and a...
research
∙
02/01/2021
On the dichromatic number of surfaces
In this paper, we give bounds on the dichromatic number χ⃗(Σ) of a surfa...
research
∙
09/28/2020
Extension of Gyarfas-Sumner conjecture to digraphs
The dichromatic number of a digraph D is the minimum number of colors ne...
research
∙
08/12/2020
On the tree-width of even-hole-free graphs
The class of all even-hole-free graphs has unbounded tree-width, as it c...
research
∙
05/19/2020
Graphs with no induced house nor induced hole have the de Bruijn-Erdős property
A set of n points in the plane which are not all collinear defines at le...
research
∙
01/11/2020
Grundy Coloring friends, Half-Graphs, Bicliques
The first-fit coloring is a heuristic that assigns to each vertex, arriv...
research
∙
06/01/2018
Extension Complexity of the Correlation Polytope
We prove that for every n-vertex graph G, the extension complexity of th...
research
∙
02/15/2018
Distributed coloring in sparse graphs with fewer colors
This paper is concerned with efficiently coloring sparse graphs in the d...
research
∙
10/17/2017