**Abstract.** We say that a graph $G$ is $(\aleph_0,\kappa)$-chromatic if $\text{Chr}(G)=\kappa$, while $\text{Chr}(G’)\le\aleph_0$ for any subgraph $G’$ of $G$ of size $<|G|$.

The main result of this paper reads as follows.

If $\square_\lambda+\text{CH}_\lambda$ holds for a given uncountable cardinal $\lambda$, then for every cardinal $\kappa\le\lambda$, there exists an $(\aleph_0,\kappa)$-chromatic graph of size $\lambda^+$.

We also study $(\aleph_0,\lambda^+)$-chromatic graphs of size $\lambda^+$. In particular, it is proved that if $0^\sharp$ does not exist, then for every singular strong limit cardinal $\lambda$, there exists an $(\aleph_0,\lambda^+)$-chromatic graph of size $\lambda^+$.

**Downloads:**

**Citation information:**

A. Rinot, *Chromatic numbers of graphs – large gaps*, Combinatoica, 35(2): 215-233, 2015.

That really is a simple method! Nice one Assaf!

0 likes

Thank you very much!!

0 likes

Submitted to

Combinatorica, January 2013.Accepted, April 2013.

1 likes

Hi Assaf. It is a nice paper! (By the way, none of the references I looked at had anything as detailed as your results on changing chromatic numbers.)

0 likes

Thanks a lot for checking!

p.s.

In addition to the results I told you about, I found more, including a ZFC example of an uncountably chromatic graph that can be made countably chromatic via a c.c.c. forcing, and that GCH entails analogous statements for successors of regulars above $\aleph_1$.

1 likes

It turns out there is no need for a nonreflecting stationary set!

In an upcoming paper with Chris Lambie-Hanson, we shall show that moreover the existence of an almost countably chromatic graph of size and chromatic number $\kappa$ is consistent with the reflection of the

countable coloring numberfor graphs of size $\kappa$.0 likes