Pith. sign in

On the growth rate of chromatic numbers of finite subgraphs

· 2019 · math.LO · arXiv 1902.08177

1 Pith paper cite this work. Polarity classification is still indexing.

1 Pith paper citing it
open full Pith review browse 1 citing papers arXiv PDF
abstract

We prove that, for every function $f:\mathbb{N} \rightarrow \mathbb{N}$, there is a graph $G$ with uncountable chromatic number such that, for every $k \in \mathbb{N}$ with $k \geq 3$, every subgraph of $G$ with fewer than $f(k)$ vertices has chromatic number less than $k$. This answers a question of Erd\H{o}s, Hajnal, and Szemeredi.

fields

math.CO 1

years

2019 1

verdicts

CONDITIONAL 1

representative citing papers

On the growth rate of dichromatic numbers of finite subdigraphs

math.CO · 2019-08-20 · conditional · novelty 7.0

For every growth function f, there are uncountably dichromatic digraphs of size continuum in which every (n+2)-dichromatic finite subdigraph has at least f(n) vertices, and it is consistent with arbitrarily large continuum that the same holds with optimal size for every infinite cardinal kappa up…

citing papers explorer

Showing 1 of 1 citing paper.

  • On the growth rate of dichromatic numbers of finite subdigraphs math.CO · 2019-08-20 · conditional · none · ref 2 · internal anchor

    For every growth function f, there are uncountably dichromatic digraphs of size continuum in which every (n+2)-dichromatic finite subdigraph has at least f(n) vertices, and it is consistent with arbitrarily large continuum that the same holds with optimal size for every infinite cardinal kappa up…