solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看11243次
New Bounds for the Dichromatic Number of a Digraph. (arXiv:1810.09427v1 [math.CO])
来源于:arXiv
The dichromatic number of a digraph $D$, denoted by $\chi_A(D)$, is the
minimum $k$ such that $D$ admits a $k$-coloring of its vertex set in such a way
that each color class is acyclic.
In 1976, Bondy proved that the chromatic number of a digraph $D$ is at most
its circumference, the length of a longest cycle.
In this paper we will construct three graphs from $D$ whose chromatic numbers
will bound $\chi_A(D)$.
Moreover, we prove: i) for integers $k\geq 2$, $s\geq 1$ and $r_1, \ldots,
r_s$ with $k\geq r_i\geq 0$ and $r_i\neq 1$ for each $i\in[s]$, that if all
cycles in $D$ have length $r$ modulo $k$ for some $r\in\{r_1,\ldots,r_s\}$,
then $\chi_A(D)\leq 2s+1;$ ii) if $D$ has girth $g$, the length of a shortest
cycle, and circumference $c$, then $\chi_A(D)\leq \lceil \frac{c-1}{g-1} \rceil
+1$, which improves, substantially, the bound proposed by Bondy; iii) if $D$
has girth $g$ and there are integers $k$ and $p,$ with $k\geq g-1\geq p\geq 1$
such that $D$ contains no cycle of length $r$ 查看全文>>