1
$\begingroup$

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?

$\endgroup$
0

1 Answer 1

5
$\begingroup$

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.

$\endgroup$
5
  • 3
    $\begingroup$ 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. $\endgroup$
    – lambda
    Jun 20, 2021 at 17:27
  • 1
    $\begingroup$ @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. $\endgroup$
    – GH from MO
    Jun 20, 2021 at 21:24
  • 2
    $\begingroup$ Not only the coloring number of $G$ but even the list chromatic number (choice number) $\chi_\ell(G)$ is infinite. $\endgroup$
    – bof
    Jun 20, 2021 at 23:33
  • 1
    $\begingroup$ 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}$. $\endgroup$
    – bof
    Jun 21, 2021 at 6:22
  • $\begingroup$ @bof: Good point. I was sure my proof was not the simplest one! $\endgroup$
    – GH from MO
    Jun 21, 2021 at 6:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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