A note on coloring digraphs of large girth

DOI10.1016/J.DAM.2020.08.003MaRDI QIDQ2004076zbMATH OpenOpenAlexFDO

Authors Raphael Steiner

Publication date 14 October 2020

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2004.01925

zbMATH Keywords

dichromatic numberdigirthdigraphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20)

Abstract: The digirth of a digraph is the length of a shortest directed cycle. The dichromatic number $vecchi(D)$ of a digraph $D$ is the smallest size of a partition of the vertex-set into subsets inducing acyclic subgraphs. A conjecture by Harutyunyan and Mohar states that $vecchi(D)leleftlceilfracDelta4ightceil+1$ for every digraph $D$ of digirth at least $3$ and maximum degree $Delta$. The best known partial result by Golowich shows that $vecchi(D)lefrac25Delta+O(1)$. In this short note we prove for every $gge2$ that if $D$ is a digraph of digirth at least $2g-1$ and maximum degree $Delta$, then $vecchi(D)le(frac13+frac13g)Delta+O_g(1)$. This improves the bound of Golowich for digraphs without directed cycles of length at most $10$.

Review text

Let \(D\) be a digraph. Vertices \(v_1,\dots,v_k\) induce a directed cycle if \((v_i,v_{i+1})\) and \((v_k,v_1)\) are arcs of \(D\) for every \(i\in\{1,\dots,k-1\}\). The digirth \(\vec{g}(D)\) of \(D\) is the length of a shortest directed cycle and if there is no directed cycle in \(D\) we set digirth to be infinite. A partition \(\{S_1,\dots,S_\ell\}\) of \(V(D)\) is called dichromatic partition if every digraph induced by \(S_i\), \(i\in\{1,\dots,\ell\}\) has an infinite digirth. The dichromatic number \(\vec{\chi}(D)\) is the minimum \(\ell\) for which there exists a dichromatic partition of \(V(D)\) to \(\ell\) sets. The author shows in this short note that \(\vec{\chi}(D)\leq (\frac{1}{3}+\frac{1}{3g})\Delta+(g+1)\), where \(g\geq 2\) is a natural number and \(D\) is a digraph with \(\vec{g}(D)\geq 2g-1\) and maximum degree \(\Delta\). This improves the bound of \textit{N. Golowich} [Discrete Math. 339, No. 6, 1734--1743 (2016; Zbl 1333.05110)] for digraphs with \(\vec{g}(D)>10\).

Recommendations

• Two results on the digraph chromatic number
• Digraph girth via chromatic number
• New Bounds for the Dichromatic Number of a Digraph
• Strengthened Brooks' theorem for digraphs of girth at least three
• The \(m\)-degenerate chromatic number of a digraph

Cites work

• Acyclic systems of representatives and acyclic colorings of digraphs
• Coloring tournaments: from local to global
• Dichromatic number and fractional chromatic number
• Eigenvalues and colorings of digraphs
• scientific article; zbMATH DE number 3243267 (Why is no real title available?)
• List coloring digraphs
• Perfect digraphs
• Planar digraphs of digirth five are 2-colorable
• Planar digraphs of digirth four are 2-colorable
• Strengthened Brooks' theorem for digraphs of girth at least three
• Subdivisions in digraphs of large out-degree or large dichromatic number
• The \(m\)-degenerate chromatic number of a digraph
• The dichromatic number of a digraph

Cited in

(23)

• Extension of Gyárfás-Sumner conjecture to digraphs
• Digraphs with all induced directed cycles of the same length are not \(\vec{\chi}\)-bounded
• Chordal directed graphs are not \(\chi\)-bounded
• Reducing the dichromatic number via cycle reversions in infinite digraphs
• Homomorphisms to digraphs with large girth and oriented colorings of minimal series-parallel digraphs
• An extension of Richardson's theorem in m-colored digraphs
• Uniquely \(D\)-colourable digraphs with large girth. II: Simplification via generalization
• The \(m\)-degenerate chromatic number of a digraph
• Decomposing and colouring some locally semicomplete digraphs
• Digraph girth via chromatic number
• Planar digraphs of digirth five are 2-colorable
• Uniquely D-colourable digraphs with large girth
• Two results on the digraph chromatic number
• Coloring digraphs with forbidden cycles
• On the maximum arc-chromatic number of digraphs with bounded outdegrees or indegrees
• Planar digraphs of digirth four are 2-colorable
• A short construction of highly chromatic digraphs without short cycles
• Four proofs of the directed Brooks' theorem
• Strengthened Brooks' theorem for digraphs of girth at least three
• Coloring \(k\)-partite sparse digraphs
• Redicolouring digraphs: directed treewidth and cycle-degeneracy
• \((\overrightarrow{P_6}\), triangle)-free digraphs have bounded dichromatic number
• Clique number of tournaments

This page was built for publication: A note on coloring digraphs of large girth

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