File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Coloring digraphs with forbidden cycles

TitleColoring digraphs with forbidden cycles
Authors
Issue Date2015
PublisherElsevier, Inc. The Journal's web site is located at http://www.elsevier.com/locate/jctb
Citation
Journal of Combinatorial Theory, Series B, 2015, v. 115, p. 210-223 How to Cite?
AbstractLet 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.
Persistent Identifierhttp://hdl.handle.net/10722/217064

 

DC FieldValueLanguage
dc.contributor.authorChen, Z-
dc.contributor.authorMa, J-
dc.contributor.authorZang, W-
dc.date.accessioned2015-09-18T05:47:18Z-
dc.date.available2015-09-18T05:47:18Z-
dc.date.issued2015-
dc.identifier.citationJournal of Combinatorial Theory, Series B, 2015, v. 115, p. 210-223-
dc.identifier.urihttp://hdl.handle.net/10722/217064-
dc.description.abstractLet 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.-
dc.languageeng-
dc.publisherElsevier, Inc. The Journal's web site is located at http://www.elsevier.com/locate/jctb-
dc.relation.ispartofJournal of Combinatorial Theory, Series B-
dc.titleColoring digraphs with forbidden cycles-
dc.typeArticle-
dc.identifier.emailZang, W: wzang@maths.hku.hk-
dc.identifier.authorityZang, W=rp00839-
dc.identifier.doi10.1016/j.jctb.2015.06.001-
dc.identifier.scopuseid_2-s2.0-84939266092-
dc.identifier.hkuros252039-
dc.identifier.volume115-
dc.identifier.spage210-
dc.identifier.epage223-
dc.publisher.placeSan Diego, USA-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats