3
$\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)$?

$\endgroup$
  • $\begingroup$ It is the minimal degree - sorry, I should have included this in the post, will do. $\endgroup$ – Dominic van der Zypen Nov 1 '17 at 14:11
  • $\begingroup$ Are $H$ restricted to be finite subgraphs? $\endgroup$ – Mikhail Tikhomirov Nov 1 '17 at 14:22
  • 7
    $\begingroup$ A line infinite in both directions seems to be a counterexample. $\endgroup$ – Emil Jeřábek Nov 1 '17 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 '17 at 16:36
5
$\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$.

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