Aboulker et al. proved that a digraph with large enough dichromatic number contains any fixed digraph as a subdivision. The dichromatic number of a digraph is the smallest order of a partition of its vertex set into acyclic induced subdigraphs. A digraph is dicritical if the removal of any arc or vertex decreases its dichromatic number. In this...
-
February 21, 2024 (v1)PublicationUploaded on: February 24, 2024
-
June 28, 2023 (v1)Conference paper
We prove that every 4-dicritical oriented graph on n vertices has at least $(\frac{10}{3}+\frac{1}{51})n - 1$ arcs.
Uploaded on: December 25, 2023 -
April 29, 2024 (v1)Journal article
The dichromatic number of a digraph is the minimum number of colours needed to colour the vertices of a digraph such that each colour class induces an acyclic subdigraph. A digraph is ‐dicritical if and each proper subdigraph of satisfies . For integers and , we define (resp., ) as the minimum number of arcs possible in a ‐dicritical digraph...
Uploaded on: August 2, 2024 -
August 24, 2021 (v1)Book section
In this paper, we give bounds on the dichromatic number − → χ (Σ) of a surface Σ, which is the maximum dichromatic number of an oriented graph embeddable on Σ. We determine the asymptotic behaviour of − → χ (Σ) by showing that there exist constants a1 and a2 such that, a1 √ −c log(−c) ≤ − → χ (Σ) ≤ a2 √ −c log(−c) for every surface Σ with Euler...
Uploaded on: December 3, 2022 -
2021 (v1)Report
In this paper, we give bounds on the dichromatic number $\vec{\chi}(\Sigma)$ of a surface $\Sigma$, which is the maximum dichromatic number of an oriented graph embeddable on $\Sigma$. We determine the asymptotic behaviour of $\vec{\chi}(\Sigma)$ by showing that there exist constants $a_1$ and $a_2$ such that, $ a_1\frac{\sqrt{-c}}{\log(-c)}...
Uploaded on: December 4, 2022 -
January 27, 2022 (v1)Journal article
In this paper, we give bounds on the dichromatic number χ(Σ) of a surface Σ, which is the maximum dichromatic number of an oriented graph embeddable on Σ. We determine the asymptotic behaviour of χ(Σ) by showing that there exist constants a 1 and a 2 such that, a 1 √ −c log(−c) χ(Σ) a 2 √ −c log(−c) for every surface Σ with Euler characteristic...
Uploaded on: February 22, 2023 -
February 13, 2023 (v1)Publication
The dichromatic number ⃗ χ(D) of a digraph D is the least integer k such that D can be partitioned into k directed acyclic digraphs. A digraph is k-dicritical if ⃗ χ(D) = k and each proper subgraph D ′ of D satisfies ⃗ χ(D) ≤ k − 1. An oriented graph is a digraph with no directed cycle of length 2. For integers k and n, we denote by o k (n) the...
Uploaded on: February 27, 2023 -
August 28, 2023 (v1)Conference paper
The inversion of a set X of vertices in a digraph D consists of reversing the direction of all arcs of D⟨X⟩. We study sinv ′ k (D) (resp. sinv k (D)) which is the minimum number of inversions needed to transform D into a k-arcstrong (resp. k-strong) digraph and sinv ′ k (n) = max{sinv ′ k (D) | D is a 2k-edge-connected digraph of order n}. We...
Uploaded on: December 25, 2023