# Uncountably chromatic Every uncountably chromatic graph contains subgraphs isomorphic to the following: - Every bipartite graph of the form $[[k,\omega_{1}]]$ for $k<\omega$. [[Erdős, Hajnal - On chromatic number of graphs and set-systems]] - In [[Thomassen - Cycles in graphs of uncountable chromatic number]] it is shown that there is also a single vertex which is contained in copies of all finite bipartite graphs. - [[Hajnal, Komjáth - What must and what need not be contained in a graph of uncountable chromatic number]] Presents the following graph: ![[Hajnal, Komjáth - What must and what need not be contained in a graph of uncountable chromatic number#$ Gamma$]] - Some generalizations of this can be found in [[Komjáth - The Colouring Number#Obligatory graphs]] - For every uncountably chromatic graph there is some $n$ such that all odd circuits of length $2j+1$ for $n<j<\omega$ appear in the graph. [[Erdős, Hajnal, Shelah - On some general properties of chromatic numbers]] - In [[Thomassen - Cycles in graphs of uncountable chromatic number]] it is shown that there is also a single vertex contained in all large enough odd circuits. ## Limitations - For every $n<\omega$ there are uncountably chromatic graphs with no odd circuits of length lt;n$. [[Erdős, Hajnal - On chromatic number of graphs and set-systems]] - In particular, every obligatory graph for uncountably chromatic graphs must be bipartite. - The following graph is *not* obligatory: ![[Hajnal, Komjáth - What must and what need not be contained in a graph of uncountable chromatic number#$ Delta$]] # Uncountable coloring number [[Bowler, Carmesin, Komjáth, Reiher - The Colouring Number of Infinite Graphs]] > [!info] Definition > Let $\kappa>\omega$ be regular. > A graph $G$ with set of vertices $\kappa$ is said to be an *$\omega$-ladder* if there is a stationary set $T$ such that each $\alpha\in T$ has at least $\omega$ neighbors in $\alpha$. > > Also, every graph isomorphic to such a graph is regarded as a $\omega$-ladder. > > There are two types of ladders: > 1. An *$\omega$-obstruction of type I* is a bipartite graph $H$ with bipartition $(A, B)$ such that for some cardinal $\lambda\geq\omega$ we have > - $|A| = \lambda$, $|B| = \lambda^+$; > - every vertex of $B$ has at least $\omega$ neighbours in $A$; > - every vertex of $A$ has $\lambda^+$ neighbours in $B$. > 1. An *$\omega$-obstruction of type II* is a graph $G=(\kappa,E)$ such that there is a stationary set of $\alpha$ satisfying: > - $\mathrm{otp}N(\alpha)\cap \alpha=\omega$; > - $\sup N(\alpha)\cap \alpha =\alpha$. > - **Theorem.** Any graph with uncountable coloring number (and in particular every uncountably *chromatic* graph) contains an $\omega$-ladder, i.e. an $\omega$-obstruction of one of the types.