Coloring digraphs with forbidden cycles

DOI10.1016/J.JCTB.2015.06.001MaRDI QIDQ490994zbMATH OpenOpenAlexFDO

Authors Zhibin Chen, Jie Ma, Wenan Zang

Publication date 21 August 2015

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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

zbMATH Keywords

chromatic numberdigraphacyclic coloringdichromatic numbercycle length

Mathematics Subject Classification ID

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

Abstract: Let $k$ and $r$ be two integers with $kge2$ and $kgerge1$. In this paper we show that (1) if a strongly connected digraph $D$ contains no directed cycle of length $1$ modulo $k$, then $D$ is $k$-colorable; and (2) if a digraph $D$ contains no directed cycle of length $r$ modulo $k$, then $D$ can be vertex-colored with $k$ colors so that each color class induces an acyclic subdigraph in $D$. The first result gives an affirmative answer to a question posed by Tuza in 1992, and the second implies the following strong form of a conjecture of Diwan, Kenkre and Vishwanathan: If an undirected graph $G$ contains no cycle of length $r$ modulo $k$, then $G$ is $k$-colorable if $re2$ and $(k+1)$-colorable otherwise. Our results also strengthen several classical theorems on graph coloring proved by Bondy, ErdH{o}s and Hajnal, Gallai and Roy, Gy'arf'as, etc.

Recommendations

• New Bounds for the Dichromatic Number of a Digraph
• Cycles in color-critical graphs
• Paths, cycles and circular colorings in digraphs
• Cycles with two blocks in \(k\)-chromatic digraphs
• A note on coloring digraphs of large girth

Cites work

• scientific article; zbMATH DE number 3687449 (Why is no real title available?)
• scientific article; zbMATH DE number 3257176 (Why is no real title available?)
• A Min-Max Theorem on Tournaments
• A bound on the chromatic number using the longest odd cycle length
• Circular colorings of edge-weighted graphs
• Circumference, chromatic number and online coloring
• Cycle length parities and the chromatic number
• Cycle lengths and chromatic number of graphs
• Cycles of length 0 modulo 4 in graphs
• Diconnected Orientations and a Conjecture of Las Vergnas
• Digraph girth via chromatic number
• Gallai's theorem for list coloring of digraphs
• Graph coloring in linear time
• Graph theory
• Graphs with \(k\) odd cycle lengths
• Nombre chromatique et plus longs chemins d'un graphe
• On chromatic number of graphs and set-systems
• Problems on cycles and colorings
• Strengthened Brooks' theorem for digraphs of girth at least three
• The circular chromatic number of a digraph
• The dichromatic number of a digraph
• Tournaments and colouring
• Two results on the digraph chromatic number

Cited in

(19)

• \((\overrightarrow{P_6}\), triangle)-free digraphs have bounded dichromatic number
• Subdivisions with congruence constraints in digraphs of large chromatic number
• Cycles and new bounds for the chromatic number
• Cycles in color-critical graphs
• On coloring digraphs with forbidden induced subgraphs
• Congruence of cycle lengths and chromatic number
• A strengthening on odd cycles in graphs of given chromatic number
• 4-Chromatic graphs have at least four cycles of length 0 mod 3
• Planar digraphs of digirth five are 2-colorable
• A dichotomy theorem for circular colouring reconfiguration
• Cycle lengths and minimum degree of graphs
• scientific article; zbMATH DE number 5763169 (Why is no real title available?)
• Cycles with two blocks in \(k\)-chromatic digraphs
• Coloring dense digraphs
• Paths, cycles and circular colorings in digraphs
• Monochromatic directed walks in arc-colored directed graphs
• The \(m\)-degenerate chromatic number of a digraph
• A quick way to verify if a graph is 3-colorable
• Complete directed minors and chromatic number

This page was built for publication: Coloring digraphs with forbidden cycles

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