# Upper bound on the list chromatic number of $d$-degenerate graphs

It can be proved that $\chi(G)\le d+1$ if $G$ is $d$-degenerate, but can we also say that $\chi_\ell(G)\le d+1$, in general[note 1]? Here, $\chi(G)$ is the chromatic number of $G$ and $\chi_\ell(G)$ is the list-chromatic number.

I did not think it was immediately obvious (if indeed it is true), since $\chi_\ell(G)$ can be arbitrarily large compared to $\chi(G)$. Moreover, I could not find any proofs via Google, nor was the list chromatic number even mentioned on the Wikipedia article on $d$-degeneracy. My attempt at a proof is below, am I correct?

[Note 1] I believe this only holds true if $G$ is finite? My proof does, in its current form, since I work backwards $v_n$ to $v_1$ in constructing my vertex-ordering, and forwards $v_1$ to $v_n$ when colouring them... There might be a better algorithm that works more generally.

Proof(?). Let $G$ be $d$-degenerate. I construct an ordering of the vertices $v_1,\ldots,v_n$ such that $v_i$ has at most $d$ neighbours among $v_1,\ldots,v_{i-1}$ (similar to what is pictured below, taken from Wikipedia). To do this, follow this algorithm:

1. Let $V_n=V(G)$ be the vertex set of $G$.
2. Choose $v_n\in V_n$ as a vertex $v_n$ that has degree at most $d$ in the graph induced by $V_n$.
3. Stop if $n=1$. Otherwise let $V_{n-1}=V_n-v_n$, and go back to (2.).

Now let $L\colon V(G)\to 2^\Bbb{N}$ be a $(d+1)$-list-assignment on $V(G)$ (i.e. $|L(v)|=d+1$ for all $v$). We can construct an $L$-colouring by working from $v_1$ through to $v_n$, and at every stage, at most $d$ colours will be "unavailable" — at most $d$ neighbours have already been coloured, only those to the "left".

Since $L$ was arbitrary, $\chi_\ell(G)\le d+1$.

• @bof the definition I was usuing was "every subgraph has a vertex of degree at most $d$". Would this be inequivalent in the infinite case? – Szmagpie May 27 '16 at 15:56

## 1 Answer

Your proof is fine, and the result is well known. The inequality can be strict, e.g., when $G=K_{3,3}.$

For a finite graph $G$ and a finite cardinal $d$ the following statements are easily seen to be equivalent:

1. for every nonempty set $S\subseteq V(G)$ there is a vertex $v\in S$ such that $|N(v)\cap S|\le d;$

2. $V(G)$ can be totally ordered so that each vertex is preceded by at most $d$ of its neighbors.

A finite graph $G$ is $d$-degenerate if it satisfies either of those equivalent conditions.

For an infinite (or finite) graph $G$ and a finite cardinal $d,$ the following statements are equivalent:

1. every finite subgraph of $G$ is $d$-degenerate;

2. for every nonempty finite set $S\subseteq V(G)$ there is a vertex $v\in S$ such that $|N(v)\cap S|\le d;$

3. $V(G)$ can be totally ordered so that each vertex is preceded by at most $d$ of its neighbors.

For finite $d,$ an arbitrary graph $G$ is $d$-choosable (that is, $\chi_\ell(G)\le d$) if every finite subgraph of $G$ is $d$-choosable; this is the list-colouring version of the De Bruijn–Erdős theorem. Thus an infinite graph satisfying any of the equivalent conditions 3–5 is $d$-choosable.

The natural generalization of your observation to the case of infinitely many colors is best expressed in terms of the colouring number $\operatorname{Col}(G)$ which was introduced by P. Erdős and A. Hajnal in their paper On chromatic number of graphs and set-systems, Acta Math. Acad. Sci. Hungar. 17 (1966), 61-99. Namely, $\chi_\ell(G)\le\operatorname{Col}(G),$ where $\operatorname{Col}(G)$ is defined as the least cardinal $\kappa$ for which there is a well-ordering $\lt$ of $V(G)$ such that for each vertex $v$ we have $|N(v)\cap\{u:u\lt v\}|\lt\kappa.$

Note that, for a finite cardinal $d,$ a finite graph $G$ is $d$-degenerate if and only if $\operatorname{Col}(G)\le d+1.$