On the minimum number of arcs in $4$-dicritical oriented graphs
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866929329009590272 |
|---|---|
| author | Havet, Frédéric Picasarri-Arrieta, Lucas Rambaud, Clément |
| author_facet | Havet, Frédéric Picasarri-Arrieta, Lucas Rambaud, Clément |
| contents | The dichromatic number $\vecχ(D)$ of a digraph $D$ 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 $D$ is $k$-dicritical if $\vecχ(D) = k$ and each proper subdigraph $H$ of $D$ satisfies $\vecχ(H) < k$.
For integers $k$ and $n$, we define $d_k(n)$ (respectively $o_k(n)$) as the minimum number of arcs possible in a $k$-dicritical digraph (respectively oriented graph). Kostochka and Stiebitz have shown that $d_4(n) \geq \frac{10}{3}n -\frac{4}{3}$. They also conjectured that there is a constant $c$ such that $o_k(n) \geq cd_k(n)$ for $k\geq 3$ and $n$ large enough. This conjecture is known to be true for $k=3$ (Aboulker et al.).
In this work, we prove that every $4$-dicritical oriented graph on $n$ vertices has at least $(\frac{10}{3}+\frac{1}{51})n-1$ arcs, showing the conjecture for $k=4$. We also characterise exactly the $k$-dicritical digraphs on $n$ vertices with exactly $\frac{10}{3}n -\frac{4}{3}$ arcs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2306_10784 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | On the minimum number of arcs in $4$-dicritical oriented graphs Havet, Frédéric Picasarri-Arrieta, Lucas Rambaud, Clément Combinatorics Discrete Mathematics The dichromatic number $\vecχ(D)$ of a digraph $D$ 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 $D$ is $k$-dicritical if $\vecχ(D) = k$ and each proper subdigraph $H$ of $D$ satisfies $\vecχ(H) < k$. For integers $k$ and $n$, we define $d_k(n)$ (respectively $o_k(n)$) as the minimum number of arcs possible in a $k$-dicritical digraph (respectively oriented graph). Kostochka and Stiebitz have shown that $d_4(n) \geq \frac{10}{3}n -\frac{4}{3}$. They also conjectured that there is a constant $c$ such that $o_k(n) \geq cd_k(n)$ for $k\geq 3$ and $n$ large enough. This conjecture is known to be true for $k=3$ (Aboulker et al.). In this work, we prove that every $4$-dicritical oriented graph on $n$ vertices has at least $(\frac{10}{3}+\frac{1}{51})n-1$ arcs, showing the conjecture for $k=4$. We also characterise exactly the $k$-dicritical digraphs on $n$ vertices with exactly $\frac{10}{3}n -\frac{4}{3}$ arcs. |
| title | On the minimum number of arcs in $4$-dicritical oriented graphs |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2306.10784 |