Orientations of graphs with uncountable chromatic number

DOI10.1002/JGT.22233zbMATH Open1393.05124arXiv1608.06981OpenAlexW2962908397MaRDI QIDQ4581287FDOQ4581287

Authors: Dániel T. Soukup 

Publication date: 16 August 2018

Published in: Journal of Graph Theory (Search for Journal in Brave)

Abstract: Motivated by an old conjecture of P. ErdH{o}s and V. Neumann-Lara, our aim is to investigate digraphs with uncountable dichromatic number and orientations of undirected graphs with uncountable chromatic number. A graph has uncountable chromatic number if its vertices cannot be covered by countably many independent sets, and a digraph has uncountable dichromatic number if its vertices cannot be covered by countably many acyclic sets. We prove that consistently there are digraphs with uncountable dichromatic number and arbitrarily large digirth; this is in surprising contrast with the undirected case: any graph with uncountable chromatic number contains a 4-cycle. Next, we prove that several well known graphs (uncountable complete graphs, certain comparability graphs, and shift graphs) admit orientations with uncountable dichromatic number in ZFC. However, we show that the statement "every graph $G$ of size and chromatic number $omeg{a}_1$ has an orientation $D$ with uncountable dichromatic number" is independent of ZFC.

Full work available at URL: https://arxiv.org/abs/1608.06981

Recommendations

• Uncountable dichromatic number without short directed cycles
• scientific article; zbMATH DE number 426350
• On the growth rate of dichromatic numbers of finite subdigraphs
• Infinitely connected subgraphs in graphs of uncountable chromatic number
• On a result of Thomassen

zbMATH Keywords

partitionchromatic numberacyclicdigraphgirthorientationdichromatic number

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Coloring of graphs and hypergraphs (05C15)

Cited In (11)

• Complete oriented colourings and the oriented achromatic number
• Reducing the dichromatic number via cycle reversions in infinite digraphs
• Acyclic orientations and chromatic generating functions
• Proper orientations and proper chromatic number
• Degree constrained orientations in countable graphs
• Induced subgraphs of graphs with large chromatic number. XI. Orientations
• Uncountable dichromatic number without short directed cycles
• On the oriented chromatic number of graphs with given excess
• On the growth rate of dichromatic numbers of finite subdigraphs
• On the forced unilateral orientation number of a graph
• Cycle reversions and dichromatic number in tournaments

This page was built for publication: Orientations of graphs with uncountable chromatic number

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4581287)