1
$\begingroup$

For the chromatic number $\chi(G)$ of a simple, undirected graph, there is a "compactness" theorem by Erdős 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)$.

A converse statement would be

$(\text{S})$ Let $k>0$ be an integer. Whenever a graph $G$ has the property that every finite subgraph $G_0$ of $G$ can be colored with $k$ colors, then $G$ can be colored with $k$ colors.

Is $(\text{S})$ true?

$\endgroup$
4
  • 4
    $\begingroup$ Isn't $(S)$ the usual statement of the Erdös-De Bruijn theorem? From the second line in the wikipedia link: "It states that, when all finite subgraphs can be colored with $c$ colors, the same is true for the whole graph" $\endgroup$ Mar 14, 2020 at 8:22
  • 1
    $\begingroup$ But even if you take the statement in the question, $(S)$ is an immediate corollary. Suppose $\chi(G_0)=k$ for every finite $G_0\subset G$. Obviously $\chi(G)\geq k$. But we can't have $\chi(G)>k$ because that would be witnessed by a finite subgraph. $\endgroup$ Mar 14, 2020 at 8:26
  • 3
    $\begingroup$ This can be proven by applying compactness for 1st order logic, right? $\endgroup$ Mar 14, 2020 at 8:59
  • $\begingroup$ @Monroe that's right $\endgroup$ Mar 14, 2020 at 9:31

1 Answer 1

4
$\begingroup$

Apparently yes. By googling, I found the assertion in this 1951 paper of de Bruijn and Erdős, and the first page contains several further references.

$\endgroup$

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.