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

Question. Does the same hold for infinite graphs?


1 Answer 1


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

  • $\begingroup$ Thanks for taking the time to write this up so carefully! $\endgroup$ Mar 1, 2017 at 13:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.