z-logo
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 .

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here
Accelerating Research

Address

John Eccles House
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom