Subdivisions of oriented cycles in digraphs with large chromatic number. Issue 4 (30th April 2018)

• Record Type: Journal Article
• Authors: Cohen, Nathann; Havet, Frédéric; Lochet, William; Nisse, Nicolas
• Is Part Of: Journal of graph theory. Volume 89:Issue 4(2018)
• Page Start: 439
• Page End: 456
• Publication Date: 2018-04-30
• Subjects: coloring -- digraph -- subdivision; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.22360
• Languages: English
• ISSNs: 0364-9024

Abstract

Abstract: An oriented cycle is an orientation of a undirected cycle. We first show that for any oriented cycle C, there are digraphs containing no subdivision of C (as a subdigraph) and arbitrarily large chromatic number. In contrast, we show that for any C a cycle with two blocks, every strongly connected digraph with sufficiently large chromatic number contains a subdivision of C . We prove a similar result for the antidirected cycle on four vertices (in which two vertices have out‐degree 2 and two vertices have in‐degree 2).