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

digraphsdichromatic numberdigirth

Mathematics Subject Classification ID

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

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$.

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

• scientific article; zbMATH DE number 3243267 (Why is no real title available?)
• 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
• 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

(22)

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

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)