Coloring digraphs with forbidden cycles

DOI10.1016/J.JCTB.2015.06.001zbMATH Open1319.05050arXiv1403.8127OpenAlexW2124145403MaRDI QIDQ490994FDOQ490994

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)

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.

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

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

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)

Cites Work

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

Cited In (19)

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

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)