Premium
Subdivisions of oriented cycles in digraphs with large chromatic number
Author(s) -
Cohen Nathann,
Havet Frédéric,
Lochet William,
Nisse Nicolas
Publication year - 2018
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22360
Subject(s) - subdivision , digraph , combinatorics , chromatic scale , mathematics , degree (music) , wheel graph , undirected graph , discrete mathematics , graph , graph power , physics , line graph , archaeology , history , acoustics
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).