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^+$.


[No arXiv entry]

Citation information:

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

This entry was posted in Compactness, Infinite Graphs, Publications 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!


  2. saf says:

    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.)


      • saf says:

        Thanks a lot for checking!

        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$.


  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$.


Leave a Reply

Your email address will not be published. Required fields are marked *