A coin graph is a graph that can be represented by a set of disjoint, except possibly touching, unit disks in the plane (i.e. the disks are the vertices and the edges correspond to the pairs that touch each other). It's easy to show by induction that $\chi(G)\leq4$ for every coin graph $G$, as there's always a vertex of degree at most 3.
My question is: what is the smallest order (i.e. the number of vertices) of a 4-chromatic coin graph?
In this paper by Erdos http://www.renyi.hu/~p_erdos/1987-27.pdf there is a coin graph of order 19 that is 4-chromatic (see Figure 1) by I doubt it's the smallest one (it was constructed for a different purpose, having to do with the independence number). The question I asked was proposed for an IMO competition in 1979, see p. 138 question 73 in Djukic, Jankovic, Matic, Petrovic: the IMO Compendium (there is no solution there, however).
Clearly, coin graphs are also unit distance graphs, for the definition see http://en.wikipedia.org/wiki/Unit_distance_graph. The smallest 4-chromatic unit-distance graph is probably the Moser spindle http://en.wikipedia.org/wiki/Moser_spindle that has 7 vertices.
There is a similar notion of matchstick graphs: those are unit distance graphs drawn in the plane with non-crossing straight-line segments, see http://en.wikipedia.org/wiki/Matchstick_graph Note that the Moser spindle is NOT a matchstick graph, although it's planar and unit-distance.
The second (related) question is: what is the smallest order of a 4-chromatic matchstick graph?
I think the answer (to the second question) is 8.
Best Answer
Flo's example with 11 is best possible. Let $G$ be a minimal coin-graph which chromatic number four. Then $G$ does not have a cut vertex, nor a vertex of degree at most two. Moreover, there does not exist a separation $(A, B)$ of $G$ of order two with $G[A \cap B]$ an edge (as opposed to a pair of non-adjacent vertices). Otherwise we could 3-color $G[A]$ and $G[B]$ and glue the colorings together to get a coloring of $G$.
Since $G$ is 2-connected, every face is bounded by a cycle. Consider the cycle $C$ bounding the infinite face. The cycle $C$ must be induced, as otherwise there is a 2-separation whose cut set is an edge. $G$ has no vertex of degree two, so every vertex of $C$ has a neighbor in $V(G) - V(C)$ (and specifically, there is at least one such vertex).
If there is exactly one vertex in $V(G) - V(C)$, then it is adjacent every vertex of $C$ and $G$ is a wheel on 7 vertices which is 3-colorable. Thus, there exist at least two vertices in $V(G) - V(C)$. However, then $|V(C)| \ge 8$. If $|V(G)| \le 10$, then $|V(C)| = 8$, and there are exactly two vertices in $V(G) - V(C)$. It follows that the graph $G$ must be equal to an 8-cycle $C$ with vertices $v_1, \dots, v_8$ and two additional vertices $x, y$, each adjacent to a subset of the vertices $\{v_1, \dots, v_8\}$.
For each of the vertices $x$ and $y$, their neighbors must form a subpath of $C$, say $P_x$ and $P_y$. The paths $P_x$ and $P_y$ can intersect only at their endpoints. Given that $G$ is a coin graph, $|V(P_x)| \le 5$ and $|V(P_y)| \le 5$, and we see now that there are two possible cases: either $|V(P_x)| = |V(P_y)| = 5$ and $P_x$ and $P_y$ have both endpoints in common, or alternatively, $|V(P_x)| = |V(P_y)| = 4$ and $P_x$ and $P_y$ are disjoint. In either case, the resulting graph is 3-colorable, a contradiction.