Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Imagine you have a finite number of "sites" $S$ in the positive quadrant of the integer lattice $\mathbb{Z}^2$, and from each site $s \in S$, one connects $s$ to every lattice point to which it has a clear line of sight, in the sense used in my earlier question: No other lattice point lies along that line-of-sight. This creates a (highly) nonplanar graph; here $S=\{(0,0),(5,2),(3,7),(11,6)\}$:
   Visib4PtsCrossing
Now, for every pair of edges that properly cross in this graph, delete the longer edge, retaining the shorter edge. In the case of ties, give preference to the earlier site, in an initial sorting of the sites. The result is a planar graph, because all edge crossings have been removed:
   Visib4PtsPlanar

Q1. Is this graph $4$-colorable?

Some nodes of this graph (at least those on the convex hull) have a (countably) infinite degree. More generally,

Q2. Is every infinite planar graph $4$-colorable? Which types of "infinite planar graphs" are $4$-colorable?

The context here is that I am considering a type of "lattice visibility Voronoi diagram." One can ask many specific questions of this structure, but I'll confine myself to the $4$-coloring question, which may have broader interest.

share|improve this question
    
When you say four coloring, I think of political maps and coloring regions. Do you mean assigning colors to faces, edges or vertices? –  The Masked Avenger Dec 15 '13 at 2:25
    
I meant: 4-coloring the vertices so that no two adjacent vertices are assigned the same color. Sorry for the lack of clarity. –  Joseph O'Rourke Dec 15 '13 at 2:27
1  
BTW the de Bruijn-Erdos theorem (see Johnston's answer) reduces the other famous 4-color conjecture to the finite case, i.e., when we join 2 points of the plane iff their distance is exactly 1, the graph so obtained is 4-chromatic. –  Péter Komjáth Dec 15 '13 at 15:55
add comment

3 Answers

up vote 22 down vote accepted

The answer to both questions is "yes", by the De Bruijn–Erdős theorem.

share|improve this answer
    
Thanks, Nathaniel! Does this still hold even if the number of nodes is uncountable, or the degree of a node is uncountable? (Obviously conditions beyond my particular graph.) –  Joseph O'Rourke Dec 15 '13 at 2:28
3  
@JosephO'Rourke Yes, this holds regardless of the size of the graph. The De Bruijn–Erdős theorem is a particular instance of what in combinatorics we call a compactness argument or Rado's selection principle, and its truth can be seen as a consequence of the topological compactness of (arbitrary) products of finite spaces. In the countable case, a standard argument invokes König's lemma, an idea very useful in Ramsey theory. In the uncountable case, the argument can be recast as a consequence of the compactness of propositional logic. –  Andres Caicedo Dec 15 '13 at 4:30
2  
Do the answers remain "yes" in ZF? –  Timothy Chow Dec 16 '13 at 1:33
    
@TimothyChow No, the answer changes. I'm expanding this into an answer. –  Andres Caicedo Dec 16 '13 at 2:03
    
@TimothyChow For Q1, it remains "yes", there is an explicit coloring. I expanded this into an answer. –  Jan Kyncl Dec 22 '13 at 19:16
add comment

As the other answer indicates, the yes answer to your question is known as the De Bruijn-Erdős theorem.

This holds regardless of the size of the graph. The De Bruijn–Erdős theorem is a particular instance of what in combinatorics we call a compactness argument or Rado's selection principle, and its truth can be seen as a consequence of the topological compactness of (arbitrary) products of finite spaces. In the countable case, a standard argument invokes König's lemma, an idea very useful in Ramsey theory (see here for an example).

In the uncountable case, the argument can be recast as a consequence of the compactness of propositional logic (see here for an example of how propositional compactness is used in these arguments).

The answer to whether infinite graphs have the same chromatic number as their (large) finite subgraphs changes if we omit choice. For example, Shelah and Soifer considered the graph $G=(\mathbb R^2,E)$, where $s\mathrel{E}t$ for $s,t\in\mathbb R^2$, iff $$s-t-\eta\in\mathbb Q^2$$ where $$\eta\in\{(\sqrt2,0),(0,\sqrt2),(\sqrt2,\sqrt2),(-\sqrt2,\sqrt2)\}.$$ They proved in

Saharon Shelah, and Alexander Soifer. Chromatic number of the plane & its relatives. III: Its Future. Geombinatorics, XIII (1), (2003), 41–46.

that the chromatic number of $G$ is $4$ under choice, and uncountable if all sets of reals are Lebesgue measurable. This is treated in detail in Soifer's book,

Alexander Soifer. The Mathematical Coloring Book, Mathematics of Coloring and the Colorful Life of Its Creators. Springer, New York, 2009.

Closely related, Falconer proved in

Kenneth Falconer. The realization of distances in measurable subsets covering $\mathbb R^n$, Journal of Combinatorial Theory Series A, 31 (2), (1981), 184–189

that the chromatic number of the plane (the least number of colors needed so any two points at distance one from each other have distinct colors) is at least $5$ if we require each color to be measurable. On the other hand, it is a famous open problem to determine the chromatic number of the plane (assuming choice). What we currently know is that the chromatic number is between $4$ and $7$, and that the distance-$1$ graph of any $12$ points in $\mathbb R^2$ is $4$-colorable, see

Dan Pritkin. All unit-distance graphs of order $6197$ are $6$-colorable. Journal of Combinatorial Theory Series B, 73 (2), (1998), 159–163.

share|improve this answer
    
Andres, I was aware of the Shelah-Soifer result when I posted my question about ZF, but unless I'm missing something, this doesn't directly answer the question about whether the answers to Q1 and Q2 are still "yes" in ZF. The unit-distance graph of the plane isn't planar. –  Timothy Chow Dec 16 '13 at 3:43
    
@TimothyChow Ah, yes. Good point, thanks. I do not know for planar graphs. All the examples I have end up not being planar. I'll have to think about this. –  Andres Caicedo Dec 16 '13 at 4:01
    
Doesn't the result about measurable sets imply that, assuming choice, the chromatic number is at most 5? –  Will Sawin Dec 22 '13 at 15:27
    
@WillSawin Ah, that was a typo. Thanks. –  Andres Caicedo Dec 22 '13 at 16:38
add comment

Regarding Q1: The graph is a subgraph of the visibility graph of the integer lattice. Every sublattice $x+2\mathbb{Z} \times 2\mathbb{Z}$ is an independent set in the visibility graph, and the integer lattice can be decomposed into four such sublattices (according to the parity of coordinates). This gives a proper $4$-coloring.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.