# Basic definitions and notations >[!info] Definition >An *undirected loopless graph* is a pair $G=(V(G),E(G))$ where $V(G)$ is the *vertex set* and $E(G)\subseteq [V(G)]^{2}$ (unordered pairs) is the *edge set*. >>[!note] Remark >Alternatively we can think of $E(G)$ as a binary relation on $V(G)$ which is symmetric and non-reflexive. > >Subsequently, a *graph* is an undirected loopless graph. >[!info] Definition >Let $G,H$ be graphs. >- $H$ is *subgraph* of $G$ if $V(H)\subseteq V(G)$ and $E(H)\subseteq E(G)$ >- $H$ is an *induced / spanned subgraph* of $G$ if it is a subgraph such that $E(H)=E(G)\restriction V(H)$. > That is, every two vertices in $H$ are joined iff they are joined in $G$. # The Chromatic number ## Definitions The chromatic number of a graph $G=(V,E)$, $\mathrm{Chr}(G)$, is the smallest number of colors needed to color the vertices of $G$ so that no two adjacent vertices share the same color. >[!info] Definition >Let $G=(V(G),E(G))$ a graph. >A coloring $c:V(G)\to\kappa$ is *$E(G)$-chromatic* if $xEy\to c(x)\ne c(y)$. $\mathrm{Chr}(G)$ is the least $\kappa$ such that there is an $E(G)$-chromatic coloring of $V(G)$ with $\kappa$ colors. **Theorem**. (Galvin–Komjáth) The statement that each graph has a chromatic number is equivalent to the [[Axiom of Choice]]. >[!info] Definition The *chromatic spectrum* of a graph > For a graph $G$ and a class of notions of forcing $\mathcal{P}$, set $\mathrm{Chr}_\mathcal{P} (G) := \{κ ∈ \mathrm{Card} |∃P ∈ \mathcal{P}, P\Vdash \mathrm{Chr}(G) = κ\}.$ ## Facts **Theorem (de Bruijn–Erdős)** If $n < ω$, $X$ is a graph, for every finite $W ⊆ V$ , $\mathrm{Chr}(X |W ) ≤ n$, then $\mathrm{Chr}(X ) ≤ n$. **Theorem.** Consider the graph $G := (\mathbb{R}, E)$, where $x E y$ iff $(x − y − \sqrt2) ∈ \mathbb{Q}$. It is an easy exercise to prove from ZFC that $\mathrm{Chr}(G) = 2$. However, Shelah and Soifer proved that in Solovay’s model in which every set of reals is Lebesgue measurable, the graph $G$ is uncountably chromatic! (from [[Rinot - Same graph, different universe]]) ## Uncountably chromatic graphs ![[Obligatory subgraphs#Uncountably chromatic]] # The Coloring number >[!info] Definition >The *coloring number* of a graph $G$, $\mathrm{Col}(G)$, is the least cardinal $\kappa$ such that there is a well ordering $\lhd$ of $V(G)$ such that for every vertex $x$, $|\{y\mid yEx \land y\lhd x\}|< \kappa$ Note that if $\lhd$ is as above, $c(x)=\mathrm{otp}(\{y\mid yEx \land y\lhd x\})$ witnesses that the chromatic number of $G$ is $\leq \kappa$ . So $\mathrm{Chr}(G)\leq \mathrm{Col}(G) \leq \left| V(G) \right| $ >[!note] Notation >If $\triangleleft$ is a well order of $G=(V,E)$, and $x\in G$, denote $G(x):=\{y\in G\mid yEx \land y\lhd x\}$ >[!example] >- $K_{\kappa,\kappa}$, the complete bipartite graph of size $\kappa$ has $\mathrm{Chr}(K_{\kappa,\kappa})=2$ but $\mathrm{Col}(K_{\kappa,\kappa})=\kappa$. # The List-Chromatic number The list-chromatic number of a graph $G=(G,E)$, $\mathrm{List}(G)$, is the least cardinal $\kappa$ such that for any $F:G\to [|G|]^{\kappa}$ there is an $E$-chromatic coloring $c:G\to \mu$ such that forall $v\in G$, $c(v)\in F(v)$. $\mathrm{Chr}(G)\leq \mathrm{List}(G) \leq \mathrm{Col}(G)$