Minimum number of arcs in $k$-critical digraphs with order at most $2k-1$
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913332353564672 |
|---|---|
| author | Picasarri-Arrieta, Lucas Stiebitz, Michael |
| author_facet | Picasarri-Arrieta, Lucas Stiebitz, Michael |
| contents | The dichromatic number $\vecχ(D)$ of a digraph $D$ is the least integer $k$ for which $D$ has a coloring with $k$ colors such that there is no monochromatic directed cycle in $D$. The digraphs considered here are finite and may have antiparallel arcs, but no parallel arcs. A digraph $D$ is called $k$-critical if each proper subdigraph $D'$ of $D$ satisfies $\vecχ(D')<\vecχ(D)=k$. For integers $k$ and $n$, let $\overrightarrow{\mathrm{ext}}(k,n)$ denote the minimum number of arcs possible in a $k$-critical digraph of order $n$. It is easy to show that $\overrightarrow{\mathrm{ext}}(2,n)=n$ for all $n\geq 2$, and $\overrightarrow{\mathrm{ext}}(3,n)\geq 2n$ for all possible $n$, where equality holds if and only if $n$ is odd and $n\geq 3$. As a main result we prove that if $n, k$ and $p$ are integers with $n=k+p$ and $2\leq p \leq k-1$, then $\overrightarrow{\mathrm{ext}}(k,n)=2({\binom{n}{2}} - (p^2+1))$, and we give an exact characterisation of $k$-critical digraphs for which equality holds. This generalizes a result about critical graphs obtained in 1963 by Tibor Gallai. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_03584 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Minimum number of arcs in $k$-critical digraphs with order at most $2k-1$ Picasarri-Arrieta, Lucas Stiebitz, Michael Combinatorics Discrete Mathematics The dichromatic number $\vecχ(D)$ of a digraph $D$ is the least integer $k$ for which $D$ has a coloring with $k$ colors such that there is no monochromatic directed cycle in $D$. The digraphs considered here are finite and may have antiparallel arcs, but no parallel arcs. A digraph $D$ is called $k$-critical if each proper subdigraph $D'$ of $D$ satisfies $\vecχ(D')<\vecχ(D)=k$. For integers $k$ and $n$, let $\overrightarrow{\mathrm{ext}}(k,n)$ denote the minimum number of arcs possible in a $k$-critical digraph of order $n$. It is easy to show that $\overrightarrow{\mathrm{ext}}(2,n)=n$ for all $n\geq 2$, and $\overrightarrow{\mathrm{ext}}(3,n)\geq 2n$ for all possible $n$, where equality holds if and only if $n$ is odd and $n\geq 3$. As a main result we prove that if $n, k$ and $p$ are integers with $n=k+p$ and $2\leq p \leq k-1$, then $\overrightarrow{\mathrm{ext}}(k,n)=2({\binom{n}{2}} - (p^2+1))$, and we give an exact characterisation of $k$-critical digraphs for which equality holds. This generalizes a result about critical graphs obtained in 1963 by Tibor Gallai. |
| title | Minimum number of arcs in $k$-critical digraphs with order at most $2k-1$ |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2310.03584 |