File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1016/j.jctb.2015.06.001
- Scopus: eid_2-s2.0-84939266092
- WOS: WOS:000359962200010
Supplementary
- Citations:
- Appears in Collections:
Article: Coloring digraphs with forbidden cycles
Title | Coloring digraphs with forbidden cycles |
---|---|
Authors | |
Keywords | Acyclic coloring Chromatic number Cycle length Dichromatic number Digraph |
Issue Date | 2015 |
Publisher | Elsevier, 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? |
Abstract | 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. |
Persistent Identifier | http://hdl.handle.net/10722/217064 |
ISI Accession Number ID |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Chen, Z | - |
dc.contributor.author | Ma, J | - |
dc.contributor.author | Zang, W | - |
dc.date.accessioned | 2015-09-18T05:47:18Z | - |
dc.date.available | 2015-09-18T05:47:18Z | - |
dc.date.issued | 2015 | - |
dc.identifier.citation | Journal of Combinatorial Theory, Series B, 2015, v. 115, p. 210-223 | - |
dc.identifier.uri | http://hdl.handle.net/10722/217064 | - |
dc.description.abstract | 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. | - |
dc.language | eng | - |
dc.publisher | Elsevier, Inc. The Journal's web site is located at http://www.elsevier.com/locate/jctb | - |
dc.relation.ispartof | Journal of Combinatorial Theory, Series B | - |
dc.subject | Acyclic coloring | - |
dc.subject | Chromatic number | - |
dc.subject | Cycle length | - |
dc.subject | Dichromatic number | - |
dc.subject | Digraph | - |
dc.title | Coloring digraphs with forbidden cycles | - |
dc.type | Article | - |
dc.identifier.email | Zang, W: wzang@maths.hku.hk | - |
dc.identifier.authority | Zang, W=rp00839 | - |
dc.identifier.doi | 10.1016/j.jctb.2015.06.001 | - |
dc.identifier.scopus | eid_2-s2.0-84939266092 | - |
dc.identifier.hkuros | 252039 | - |
dc.identifier.volume | 115 | - |
dc.identifier.spage | 210 | - |
dc.identifier.epage | 223 | - |
dc.identifier.isi | WOS:000359962200010 | - |
dc.publisher.place | San Diego, USA | - |