On the growth rate of dichromatic numbers of finite subdigraphs

DOI10.1016/J.DISC.2019.111735MaRDI QIDQ2286596zbMATH OpenOpenAlexFDO

Authors Attila Joó

Publication date 22 January 2020

Published in Discrete Mathematics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

dichromatic numberdirected cycleinfinite digraph

Mathematics Subject Classification ID

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

Abstract: Chris Lambie-Hanson proved recently that for every function $f:mathbbNightarrowmathbbN$ there is an $alep{h}_1$-chromatic graph $G$ of size $2^{alep{h}_1}$ such that every $(n+3)$-chromatic subgraph of $G$ has at least $f(n)$ vertices. Previously, this fact was just known to be consistently true due to P. Komj'ath and S. Shelah. We investigate the analogue of this question for directed graphs. In the first part of the paper we give a simple method to construct for an arbitrary $f:mathbbNightarrowmathbbN$ an uncountably dichromatic digraph $D$ of size $2^{alep{h}_0}$ such that every $(n+2)$-dichromatic subgraph of $D$ has at least $f(n)$ vertices. In the second part we show that it is consistent with arbitrary large continuum that in the previous theorem "uncountably dichromatic" and "of size $2^{alep{h}_0}$" can be replaced by "$kappa$-dichromatic" and "of size $kappa$" respectively where $kappa$ is universally quantified with bounds $alep{h}_{0}leqkappaleq{2}^{alep{h}_0}$.

Recommendations

• On the growth rate of chromatic numbers of finite subgraphs
• The rate of growth of the minimum clique size of graphs of given order and chromatic number
• New Bounds for the Dichromatic Number of a Digraph
• scientific article; zbMATH DE number 5901911
• Subcolorings and the subchromatic number of a graph
• ON THE DICHROMATIC INDEX OF A DIGRAPH
• On the chromatic number of random subgraphs of a certain distance graph
• scientific article; zbMATH DE number 4150191
• On the spectrum, the growth, and the diameter of a graph
• On \(r\)-dynamic chromatic number of graphs

Cites work

• A short construction of highly chromatic digraphs without short cycles
• Finite subgraphs of uncountably chromatic graphs
• On chromatic number of graphs and set-systems
• On the growth rate of chromatic numbers of finite subgraphs
• Orientations of graphs with uncountable chromatic number
• The chromatic number of infinite graphs - A survey
• The circular chromatic number of a digraph
• The dichromatic number of a digraph
• Uncountable dichromatic number without short directed cycles

Cited in

(4)

• On the growth rate of chromatic numbers of finite subgraphs
• The rate of growth of the minimum clique size of graphs of given order and chromatic number
• Orientations of graphs with uncountable chromatic number
• A dichotomy characterizing analytic digraphs of uncountable Borel chromatic number in any dimension

This page was built for publication: On the growth rate of dichromatic numbers of finite subdigraphs

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