0
$\begingroup$

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

enter image description here

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

$\endgroup$
  • $\begingroup$ @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? $\endgroup$ – Szmagpie May 27 '16 at 15:56
1
$\begingroup$

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

$\endgroup$

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.