# Graph $G=(V,E)$ with $\chi(G)$ finite and $\text{Col}(G)$ infinite

Let $$G = (V,E)$$ be a simple, undirected graph. For $$v\in V$$ we let $$N(v) = \{w \in V: \{v,w\} \in E\}$$.

We define the coloring number $$\text{Col}(G)$$ of the graph $$G$$ to be the smallest cardinal $$\kappa$$ such that there is a well-ordering $$\leq_{\text{well}}$$ on $$V$$ such that for every vertex $$v\in V$$ we have $$|N(v) \cap \{w\in V: w \leq_{\text{well}} v\}|< \kappa.$$

Question. Is there an infinite graph $$G = (V,E)$$ such that $$\chi(G)$$ is finite but $$\text{Col}(G)$$ is infinite?

Take a complete bipartite graph $$G=(V_1,V_2,E)$$ such that $$V_1$$ and $$V_2$$ are infinite. Then $$\chi(G)=2$$ and $$\text{Col}(G)$$ is infinite.

Indeed, consider any well-ordering on $$V=V_1\cup V_2$$. Either there exists a vertex with infinitely many smaller neighbors, or there exists an infinite path $$(v_1,v_2,\dotsc)$$ with increasing vertices. In the first case, $$\text{Col}(G)$$ is clearly infinite. In the second case, for any positive integer $$n$$, the vertex $$v_{2n}$$ has at least $$n$$ neighbors smaller than $$v_{2n}$$, namely $$v_1,v_3,\dotsc,v_{2n-1}$$. Therefore $$\text{Col}(G)$$ is infinite.

P.S. Thanks to @lambda for fixing this argument.

• There is clearly no such path if for instance the well-ordering is such that $V_1$ is an initial segment. I think it's probably true that there is either such a path or a vertex with infinitely many neighbours ordered before it. Jun 20, 2021 at 17:27
• @lambda: You are right, thanks for the correction. When I wrote up my argument I was secretly assuming that $\text{Col}(G)$ is finite, which then guarantees the infinite path readily. I updated my post accordingly. Jun 20, 2021 at 21:24
• Not only the coloring number of $G$ but even the list chromatic number (choice number) $\chi_\ell(G)$ is infinite.
– bof
Jun 20, 2021 at 23:33
• Any $n$-regular graph has coloring number $n+1$ since the last vertex in the ordering is preceded by $n$ of its neighbors. Since your graph $G$ contains $K_{n,n}$ as a subgraph, its coloring number is greater than $n$ for every $n$, so it's infinite. If a locally finite example were desired, you could just take a disjoint union of $K_{n,n}$.
– bof
Jun 21, 2021 at 6:22
• @bof: Good point. I was sure my proof was not the simplest one! Jun 21, 2021 at 6:39