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:
![[No arXiv entry]](/design/002_arxiv_dis.png "No arXiv entry") |
Citation information:
A. Rinot, Chromatic numbers of graphs – large gaps, Combinatorica, 35(2): 215-233, 2015.
That really is a simple method! Nice one Assaf!
Thank you very much!!
Submitted to Combinatorica, January 2013.
Accepted, April 2013.
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.)
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$.
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$.