4
$\begingroup$

For the chromatic number $\chi(G)$ of a simple, undirected graph, there is a "compactness" theorem by Erdos and De Bruijn stating that if an infinite graph $G$ has finite chromatic number, then there is a finite subgraph $G_0\subseteq G$ such that $\chi(G_0) = \chi(G)$.

For any simple, undirected graph $G=(V,E)$ we set $\text{col}(G) = \sup\{\delta(H): H\subseteq G\}+1$, where $\delta(\cdot)$ denotes the minimal degree. We have $\chi(G) \leq \text{col}(G)$ for any graph $G$. Does the compactness theorem above hold for $\text{col}(\cdot)$, that is, if $\text{col}(G)$ is finite, is there $G_0\subseteq G$ such that $\text{col}(G_0) = \text{col}(G)$?

Improve this question
$\endgroup$
4
  • $\begingroup$ It is the minimal degree - sorry, I should have included this in the post, will do. $\endgroup$
    – Dominic van der Zypen
    Nov 1, 2017 at 14:11
  • $\begingroup$ Are $H$ restricted to be finite subgraphs? $\endgroup$
    – Mikhail Tikhomirov
    Nov 1, 2017 at 14:22
  • 7
    $\begingroup$ A line infinite in both directions seems to be a counterexample. $\endgroup$
    – Emil Jeřábek
    Nov 1, 2017 at 14:36
  • 2
    $\begingroup$ The comment from @EmilJeřábek should probably be an (accepted) answer, so that the stackexchange software doesn't count this question as unanswered. $\endgroup$
    – Andreas Blass
    Nov 1, 2017 at 16:36

1 Answer 1

Reset to default
6
$\begingroup$

A line infinite in both directions has minimal degree $2$, but any its proper subgraph has minimal degree $1$ or $0$. Thus, $\mathrm{col}(G)=3$, but $\mathrm{col}(G_0)\le2$ for any proper subgraph $G_0$ of $G$.

More generally, if $G$ is the $d$-regular infinite tree, then $\mathrm{col}(G)=d+1$, but $\mathrm{col}(G_0)\le d$ for any proper subgraph $G_0$ of $G$.

Improve this answer
$\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.