0
$\begingroup$

Some background:

I know that for finite graphs, iff a graph has no odd cycle (i.e. it is bipartite), it can be $2$-colored. Similarly, a graph without $K_5$ or $K_{3,3}$ is planar, so it can be $4$-colored.

This question discusses an application of "no odd cycle" to infinite graphs (specifically, the rational and real unit distance graphs). I understand why an odd cycle would imply that the real unit distance graph is not $2$-colorable (it isn't even $3$-colorable), and kind of why "no odd cycle" should imply $2$-colorability of an infinite graph (if you try to $2$-color it you'll never run into any issues), but can is this a formal argument?

Also, say I have a finite graph without a $K_{2,3}$. This means it can't have a $K_5$ or a $K_{3,3}$, so it is planar and $4$-colorable. Is the concept of planarity necessary for these $4$-colorability arguments, and does that exist for uncountably infinite graphs? Either way, I'd like to use the same logic for a countably infinite graph (say, the unit distance graph in $\mathbb{Q}^n$) or an uncountably infinite graph (like the unit distance graph in $\mathbb{R}^2$, which is in fact free of $K_{2,3}$). Would this be a correct application of those two theorems? (I'm especially worried about the $4$-color theorem; since it ended in a finite case check, I doubt it would hold for infinite graphs)

I've never worked with infinite graphs so I'm not quite sure where to start on any of these. Anything about this that would point me in the right direction would be much appreciated.

$\endgroup$
2
$\begingroup$

The point is that a $k$-colouring of an infinite graph is also a $k$-colouring of all of its subgraphs. So a finite graph that isn't $k$-colourable can't occur as a subgraph of a $k$-colourable infinite graph.

On the other hand, the De Bruijn-Erdős theorem says that a graph whose finite subgraphs are all $k$-colourable is $k$-colourable.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for your answer! There's one thing I don't understand, however: As far as I understand it, the unit distance graph in $\mathbb{R}^2$ contains no $K_{2,3}$ because that would correspond to three distinct points having two distinct circumcenters (two points of distance $1$ away from each). Wouldn't this imply that all finite subgraphs of the unit distance graph are $4$-colorable, giving a solution to the Hadwiger-Nelson problem? $\endgroup$ – Carl Schildkraut Aug 25 '17 at 18:29
  • 2
    $\begingroup$ @CarlSchildkraut Having no $K_{2,3}$ as a subgraph is a weaker condition than having no $K_{2,3}$ as a minor, and it's the latter you would need to enforce planarity the way you seem to want. $\endgroup$ – Gregory J. Puleo Aug 25 '17 at 18:55
  • $\begingroup$ @GregoryJ.Puleo Thanks! I didn't know there was a difference, but it makes sense now. $\endgroup$ – Carl Schildkraut Aug 25 '17 at 19:03

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.