Timeline for Chromatic number of the infinite Erdős–Hajnal shift-graph
Current License: CC BY-SA 4.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 6 at 22:39 | comment | added | bof | For showing that $\chi(G_\kappa)\le\lambda\implies\kappa\le2^\lambda$ the Erdős–Rado theorem is overkill. If $f:[\kappa]^2\to\lambda$ is a proper vertex coloring of $G_\kappa$ then we can define an injection $F:\kappa\to\mathcal P(\lambda)$ by setting $F(\alpha)=\{f(\{\beta,\alpha\}):\beta\lt\alpha\}$. | |
| Mar 5 at 0:21 | comment | added | bof | @DominicvanderZypen I don't have time to look it up now, but if I remember right, the Erdős–Hajnal example of a $\kappa$-chromatic graph of order $\kappa$ (an infinite cardinal) has vertices $(a,b,c)$ where $a\lt b\lt c\lt\kappa$ and edges $\{(a,b,d),(c,e,f)\}$ where $a\lt b\lt c\lt d\lt e\lt f\lt\kappa$. I seem to recall that they call this a Specker graph. | |
| Mar 5 at 0:16 | comment | added | bof | And in fact, by the Erdős–Rado theorem, if $\kappa$ is an infinite cardinal, $\chi(G_\kappa)=\min\{\lambda:2^\lambda\ge\kappa\}$. | |
| Mar 4 at 16:34 | comment | added | Lajos Soukup | @DominicvanderZypen: Erdős and Rado constructed such graphs in "P. Erdős, R. Rado: A construction of graphs without triangles having pre-assigned order and chromatic number, J. London Math. Soc. 35 (1960), 445--448 ( MR25 #3853; Zentralblatt 97,164.)" old.renyi.hu/~p_erdos/1960-01.pdf By the way, you can download all of the papers of Erdős from the homepage of the Renyi Institute. | |
| Mar 4 at 14:38 | comment | added | Dominic van der Zypen | Wonderful, thanks Lajos! Do you happen to know how to construct a triangle-free graph on any infinite ordinal $\kappa$ with chromatic number $\kappa$? | |
| Mar 4 at 14:27 | vote | accept | Dominic van der Zypen | ||
| Mar 4 at 13:59 | history | answered | Lajos Soukup | CC BY-SA 4.0 |