# Chromatic numbers of graphs – large gaps

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.

This entry was posted in and tagged , , , , , , . Bookmark the permalink.

### 6 Responses to Chromatic numbers of graphs – large gaps

1. Dani Soukup says:

That really is a simple method! Nice one Assaf!

0 likes

• saf says:

Thank you very much!!

0 likes

2. saf says:

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

• saf says:

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

3. saf says:

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 number for graphs of size $\kappa$.

0 likes