Premium
Uncountable dichromatic number without short directed cycles
Author(s) -
Joó Attila
Publication year - 2020
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.22509
Subject(s) - uncountable set , digraph , mathematics , combinatorics , axiom , discrete mathematics , graph , directed graph , set (abstract data type) , chromatic scale , computer science , geometry , countable set , programming language
Hajnal and Erdős proved that a graph with uncountable chromatic number cannot avoid short cycles, it must contain, for example, C 4 (among other obligatory subgraphs). It was shown recently by Soukup that, in contrast of the undirected case, it is consistent that for any n < ω there exists an uncountably dichromatic digraph without directed cycles shorter than n . He asked if it is provable already in ZFC (i.e., Zermelo ‐Fraenkel set theory with the Axiom of choice). We answer his question positively by constructing for every infinite cardinal κ and n < ω a digraph of size 2 κ with dichromatic number at least κ + without directed cycles of length less than n .