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?



Graph $G=(V,E)$ with $\chi(G)$ finite and $\text{Col}(G)$ 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.


