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?

Improve this question
$\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$
    – Alessandro Codenotti
    Commented 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$
    – Alessandro Codenotti
    Commented Mar 14, 2020 at 8:26
  • 3
    $\begingroup$ This can be proven by applying compactness for 1st order logic, right? $\endgroup$
    – Monroe Eskew
    Commented Mar 14, 2020 at 8:59
  • $\begingroup$ @Monroe that's right $\endgroup$
    – Alessandro Codenotti
    Commented Mar 14, 2020 at 9:31

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .