Let $G= (V,E)$ be a simple undirected graph on $\kappa$ vertices, where $\kappa$ is a finite or infinite cardinal. Let $b:\kappa\to V$ be a bijection. We assign to $b$ the greedy coloring $c\_b$ constructed by traversing the graph in the order $b$. Formally, with recursive definition of $c\_b:\kappa \to V$:


* $c\_b(0) = 0$;
* if $\alpha\in\kappa$ and $\alpha > 0$ let 
$$c\_b(\alpha) = \min\:\big(\kappa\setminus\{c\_b(\beta): \beta \in \alpha\land \{b(\beta),b(\alpha)\}\in E\}\big).$$


We call $b$ *chromatic* if $\text{im}(c\_b) = \chi(G)$ where $\chi(G)$ is considered as a cardinal. For every finite graph there is a chromatic bijection (see [this link](https://en.wikipedia.org/wiki/Greedy_coloring#Optimal_ordering)). 


**Question**. Does the same hold for infinite graphs?



Greedy coloring for infinite graphs
Yes, the same holds for infinite graphs. I'll provide here a probably overlong proof of this.


Let $G = (V,E)$ be an infinite graph of size $\kappa$, and let $\chi(G) = \lambda$. If $\lambda = \kappa$, then any bijection is chromatic, so we may assume that $\lambda < \kappa$.


Let $c:V \rightarrow \lambda$ be a chromatic coloring. We first modify $c$ to make it "minimal" in a certain sense. To do this, we recursively define "color classes" $\langle A\_\eta \mid \eta < \lambda \rangle$ of vertices as follows. If $\xi < \lambda$ and $\langle A\_\eta \mid \eta < \xi \rangle$ has been defined, let $V\_\xi = V \setminus \bigcup\_{\eta < \xi} A\_\eta$ and define $A\_\xi \subseteq V\_\xi$ so that $(c^{-1}(\xi) \cap V\_\xi) \subseteq A\_\xi$ and $A\_\xi$ is a maximal independent subset of $V\_\xi$. Now define $c^\*:V \rightarrow \lambda$ by letting, for every $v \in V$, $c^\*(v)$ be the unique $\xi$ such that $v \in A\_\xi$. Salient features of $c^\*$, easily verified, are:


* $c^\*$ is a chromatic coloring;
* for all $v \in V$, $c^\*(v) \leq c(v)$;
* for all $v \in V$ and all $\eta < c^\*(v)$, there is $u \in V$ such that $\{u,v\} \in E$ and $c^\*(u) = \eta$.


We now show that there is a well-ordering of $V$ in order type $\kappa$ such that the greedy ordering defined along this well-ordering is $c^\*$. 


Let $V = \{v\_\alpha \mid \alpha < \kappa\}$. For all $v \in V$ and all $\eta < c^\*(v)$, let $\alpha\_{v, \eta}$ be the least ordinal $\alpha$ such that $\{v, v\_\alpha\} \in E$ and $c^\*(v\_\alpha) = \eta$. Define a function $f:V \rightarrow [V]^{<\lambda}$ by letting, for all $v \in V$, $f(v) = \{v\_{\alpha\_{v, \eta}} \mid \eta < c^\*(v)\}$. (Intuitively, $f$ chooses, for each $\eta < c^\*(v)$, one element $u$ of $V$ such that $\{u,v\} \in E$ and $c^\*(u) = \eta$.) For $v \in V$, let $\mathrm{cl}\_f(\{v\})$ denote the closure of $\{v\}$ under $f$, i.e., the smallest $Y \subseteq V$ such that $v \subseteq Y$ and, for all $v \in Y$, $f(v) \subseteq Y$. Easily, $|\mathrm{cl}\_f(\{v\})| < \max\{\lambda, \aleph\_0\}$.


Now recursively define an increasing sequence $\langle X\_\alpha \mid \alpha < \kappa \rangle$ of subsets of $V$ as follows. Let $X\_0 = \emptyset$. If $\alpha < \kappa$ and $X\_\alpha$ is given, let $X\_{\alpha+1} = X\_\alpha \cup \mathrm{cl}\_f(\{v\_\alpha\})$. If $\beta < \kappa$ is a limit ordinal, let $X\_\beta = \bigcup\_{\alpha < \beta}X\_\alpha$. Note that each $X\_\alpha$ is closed under $f$ and $|X\_\alpha| < \kappa$.


Now, for each $\alpha < \kappa$, let $Z\_\alpha = X\_{\alpha + 1} \setminus X\_\alpha$ and note that, for each $v \in V$, there is a unique $\alpha < \kappa$ such that $v \in Z\_\alpha$. Let $\prec\_\alpha$ be a well-ordering of $Z\_\alpha$ such that, if $u,v \in Z\_\alpha$ and $c^\*(u) < c^\*(v)$, then $u \prec\_\alpha v$. Define a well-ordering $\prec$ of $V$ by "gluing together" the $\prec\_\alpha$'s. More precisely, suppose $u \in Z\_\alpha$ and $v \in Z\_\beta$. Let $u \prec v$ if and only if $\alpha < \beta$ or $\alpha = \beta$ and $u \prec\_\alpha v$. Each initial segment of $\prec$ has order-type less than $\kappa$, so $\prec$ has order-type exactly $\kappa$. 


Now suppose $v \in V$. Say $v \in Z\_\alpha$, and let $\eta < c^\*(v)$. By construction, there is $u \in X\_{\alpha+1}$ such that $\{u,v\} \in E$ and $c^\*(u) = \eta$ (in particular, $v\_{\alpha\_{v, \eta}}$ is there). If $u \in X\_\alpha$, then $u \prec v$. If $u \in Z\_\alpha$, then, since $c^\*(u) < c^\*(v)$, we have $u \prec\_\alpha v$, so, again, $u \prec v$. Therefore, by recursion along the order $\prec$, one proves that the greedy coloring defined using $\prec$ is precisely $c^\*$.


