Coloring digraphs with forbidden cycles
Coloring digraphs with forbidden cycles
复制标题
DOI：
10.1016/j.jctb.2015.06.001
复制
发表时间：
2014-03
期刊：
影响因子：
--
通讯作者：
Zhibin Chen;Jie Ma;Wenan Zang
中科院分区：
文献类型：
--
作者：
Zhibin Chen;Jie Ma;Wenan Zang
设k和r是两个整数，且k≥ 2，k≥ r≥ 1.本文证明了：（1）若强连通有向图D不含模k长为1的有向圈，则D是k-可着色的;（2）若强连通有向图D不含模k长为r的有向圈，则D可以用k种颜色点着色，使得每种颜色类诱导出D中的一个无圈子有向图.我们的研究结果给出了肯定的答案Tuza在1992年提出的两个问题。此外，第二个猜想还包含了Diwan，Kenkre和Vishwanathan猜想的强形式：如果无向图G不含模k长为r的圈，则当r ≥ 2时G是k-可染的，否则G是（k+ 1）-可染的.我们的结果也加强了由邦迪，Erdés和Hajnal，Gallai和Roy，Gyárfás等证明的几个经典的图着色定理.
Let k and r be two integers with k≥ 2 and k≥ r≥ 1. 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. Our results give affirmative answers to two questions posed by Tuza in 1992. Moreover, the second one 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 r≠ 2 and (k+ 1)-colorable otherwise. Our results also strengthen several classical theorems on graph coloring proved by Bondy, Erdős and Hajnal, Gallai and Roy, Gyárfás, etc.