16
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ When you say four coloring, I think of political maps and coloring regions. Do you mean assigning colors to faces, edges or vertices? $\endgroup$
    – The Masked Avenger
    Commented Dec 15, 2013 at 2:25
  • $\begingroup$ I meant: 4-coloring the vertices so that no two adjacent vertices are assigned the same color. Sorry for the lack of clarity. $\endgroup$
    – Joseph O'Rourke
    Commented Dec 15, 2013 at 2:27
  • 2
    $\begingroup$ 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. $\endgroup$
    – Péter Komjáth
    Commented Dec 15, 2013 at 15:55

3 Answers 3

Reset to default
28
$\begingroup$

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

Improve this answer
$\endgroup$
5
  • $\begingroup$ 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.) $\endgroup$
    – Joseph O'Rourke
    Commented Dec 15, 2013 at 2:28
  • 4
    $\begingroup$ @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. $\endgroup$
    – Andrés E. Caicedo
    Commented Dec 15, 2013 at 4:30
  • 2
    $\begingroup$ Do the answers remain "yes" in ZF? $\endgroup$
    – Timothy Chow
    Commented Dec 16, 2013 at 1:33
  • $\begingroup$ @TimothyChow No, the answer changes. I'm expanding this into an answer. $\endgroup$
    – Andrés E. Caicedo
    Commented Dec 16, 2013 at 2:03
  • $\begingroup$ @TimothyChow For Q1, it remains "yes", there is an explicit coloring. I expanded this into an answer. $\endgroup$
    – Jan Kyncl
    Commented Dec 22, 2013 at 19:16
15
$\begingroup$

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

MR1985343. Shelah, Saharon; Soifer, Alexander. Chromatic number of the plane. III. Its future. Geombinatorics 13 (2003), no. 1, 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,

MR2458293 (2010a:05005). Soifer, Alexander. The mathematical coloring book. Mathematics of coloring and the colorful life of its creators. With forewords by Branko Grünbaum, Peter D. Johnson, Jr. and Cecil Rousseau. Springer, New York, 2009. xxx+607 pp. ISBN: 978-0-387-74640-1.

Closely related, Falconer proved in

MR0629593 (82m:05031). Falconer, K. J. The realization of distances in measurable subsets covering $\mathbb R^n$. J. Combin. Theory Ser. A 31 (1981), no. 2, 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), and it was not established until fairly recently that it is at least $5$.

MR3820926. de Grey, Aubrey D. N. J. The chromatic number of the plane is at least 5. Geombinatorics 28 (2018), no. 1, 18–31.

The example in de Grey's paper uses 1581 vertices; the smallest example currently known requires 529 vertices and 2670 edges, see

Heule, Marijn J. H. Trimming Graphs Using Clausal Proof Optimization. ArXiv:1907.00929.

Beyond this, we know is that the chromatic number of the plane is between $5$ and $7$, and that any unit distance graph requiring 7 colors should be reasonably large, see

MR1631999 (99c:05068). Pritikin, Dan. All unit-distance graphs of order 6197 are 6-colorable. J. Combin. Theory Ser. B 73 (1998), no. 2, 159–163.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Timothy Chow
    Commented Dec 16, 2013 at 3:43
  • $\begingroup$ @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. $\endgroup$
    – Andrés E. Caicedo
    Commented Dec 16, 2013 at 4:01
  • $\begingroup$ Doesn't the result about measurable sets imply that, assuming choice, the chromatic number is at most 5? $\endgroup$
    – Will Sawin
    Commented Dec 22, 2013 at 15:27
  • $\begingroup$ @WillSawin Ah, that was a typo. Thanks. $\endgroup$
    – Andrés E. Caicedo
    Commented Dec 22, 2013 at 16:38
13
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

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