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).
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom