Coloring digraphs with forbidden cycles

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

Author name not available (Why is that?)

Publication date: 21 August 2015

Published in: (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

zbMATH Keywords

No records found.

Mathematics Subject Classification ID

No records found.

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)