Uncountable dichromatic number without short directed cycles

Link:
Autor/in:
Erscheinungsjahr:
2020
Medientyp:
Text
Schlagworte:
  • Infinite Graphs
  • Compactification
  • Transitive
  • Graph In Graph Theory
  • Coloring
  • Graphic Methods
  • Infinite Graphs
  • Compactification
  • Transitive
  • Graph In Graph Theory
  • Coloring
  • Graphic Methods
Beschreibung:
  • Hajnal and Erdős proved that a graph with uncountable chromatic number cannot avoid short cycles, it must contain, for example, 𝐶4 (among other obligatory subgraphs). It was shown recently by Soukup that, in contrast of the undirected case, it is consistent that for any 𝑛<𝜔 there exists an uncountably dichromatic digraph without directed cycles shorter than 𝑛. 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 𝑛<𝜔 a digraph of size 2𝜅 with dichromatic number at least 𝜅+ without directed cycles of length less than 𝑛.
Lizenz:
  • info:eu-repo/semantics/openAccess
Quellsystem:
Forschungsinformationssystem der UHH

Interne Metadaten
Quelldatensatz
oai:www.edit.fis.uni-hamburg.de:publications/6c8e82b2-13aa-4980-a2c1-e871a50a47a9