Uncountable dichromatic number without short directed cycles

2019/05/02 by Joó, Attila
#Combinatorics (math.CO) #FOS: Mathematics #Logic (math.LO)

paper · doi:10.48550/arxiv.1905.00782

Abstract

A. Hajnal and P. Erdős proved that a graph with uncountable chromatic number cannot avoid short cycles, it must contain for example C₄ (among other obligatory subgraphs). It was shown recently by D. T. 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. We answer his question positively by constructing for every infinite cardinal κ and n<ω a digraph of size 2^κ with dichromatic number at least κ⁺ which does not contain directed cycles of length less than n as a subdigraph.

Related

• Orientations of graphs with uncountable chromatic number
• A note on uncountably chromatic graphs
• Two results on the digraph chromatic number
• Chordal directed graphs are not χ-bounded
• (P6, triangle)-free digraphs have bounded dichromatic number