New Bounds for the Dichromatic Number of a Digraph

MaRDI QIDQ5377790zbMATH OpenFDO

Authors Narda Cordero-Michel, Hortensia Galeana-Sánchez

Publication date 27 May 2019

Full work available at URL https://arxiv.org/abs/1810.09427, https://dmtcs.episciences.org/5505/pdf

zbMATH Keywords

acyclic coloringDFS algorithmdirected graph

Mathematics Subject Classification ID

Distance in graphs (05C12) Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20) Extremal problems in graph theory (05C35)

Abstract: The chromatic number of a graph $G$, denoted by $chi(G)$, is the minimum $k$ such that $G$ admits a $k$-coloring of its vertex set in such a way that each color class is an independent set (a set of pairwise non-adjacent vertices). The dichromatic number of a digraph $D$, denoted by $ch{i}_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. Given a digraph $D$, we will construct three different graphs whose chromatic numbers bound $ch{i}_A(D)$. Moreover, we prove: i) for integers $kgeq2$, $sgeq1$ and $r_1,ldots,r_s$ with $kgeq{r}_{i}geq0$ and $r_{i}eq1$ for each $iin[s]$, that if all cycles in $D$ have length $r$ modulo $k$ for some $rin{r}_1,ldots,r_s$, then $ch{i}_A(D)leq2s+1$; ii) if $D$ has girth $g$ and there are integers $k$ and $p$, with $kgeqg-1geqpgeq1$ such that $D$ contains no cycle of length $r$ modulo $lceilfrackpceilp$ for each $rin-p+2,ldots,0,ldots,p$, then $ch{i}_A(D)leqlceilfrackpceil$; iii) if $D$ has girth $g$, the length of a shortest cycle, and circumference $c$, then $ch{i}_A(D)leqlceilfracc-1g-1ceil+1$, which improves, substantially, the bound proposed by Bondy. Our results show that if we have more information about the lengths of cycles in a digraph, then we can improve the bounds for the dichromatic number known until now.

Recommendations

• New bounds for the chromatic number of graphs
• scientific article; zbMATH DE number 4150191
• New upper bounds for the chromatic number of a graph
• A new upper bound for the chromatic number of a graph
• Two results on the digraph chromatic number
• scientific article; zbMATH DE number 3918396
• Bounds for the dichromatic number of a generalized lexicographic product of digraphs
• A new bound on the cyclic chromatic number
• ON THE DICHROMATIC INDEX OF A DIGRAPH
• A dualistic approach to bounding the chromatic number of a graph

Cited in

(15)

• A note on coloring digraphs of large girth
• Cycles and new bounds for the chromatic number
• On the growth rate of dichromatic numbers of finite subdigraphs
• The \(m\)-degenerate chromatic number of a digraph
• Digraph girth via chromatic number
• Dichromatic number and fractional chromatic number
• Bounds for the dichromatic number of a generalized lexicographic product of digraphs
• scientific article; zbMATH DE number 4150191 (Why is no real title available?)
• scientific article; zbMATH DE number 3918396 (Why is no real title available?)
• Cycles with two blocks in k-chromatic digraphs
• On the heterochromatic number of circulant digraphs
• ON THE DICHROMATIC INDEX OF A DIGRAPH
• Coloring digraphs with forbidden cycles
• Extendiendo un resultado de coloraciones de gráficas a coloraciones de digráficas
• A study on token digraphs

This page was built for publication: New Bounds for the Dichromatic Number of a Digraph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5377790)