Are infinite planar graphs still 4-colorable?

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


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.


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.