Small 4-chromatic coin graphs

Question

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.

Answer 1

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.

Answer 2

Here is Flo Pfender's 11-coin graph (in his first comment):

---

          

---

Answer 3

About matchstick graphs:

I think Paul's proof also shows that my construction on 9 vertices is uniquely optimal for matchstick graphs.

By the same argument, the cycle $C$ bounding the infinite face must be induced, and every vertex on it has a neighbor inside the cycle.

If there is only one vertex inside $C$, the graph is the wheel on $7$ vertices, but then it is $3$-colorable.

By planarity, notice that the neighborhoods of the internal vertices on $C$ are paths which can only intersect in the end points. Thus, $G$ consists of a number (one for each internal vertex) of partial wheels, where neighboring partial wheels either overlap in a point or are connected by an edge.

If there are at least three internal vertices, as every internal vertex has degree at least $3$, this implies that $C$ has at least $6$ vertices. But in fact, $6$ is not possible, as three diamonds can not be arranged in a triangle.

So there are exactly $2$ internal vertices. Again, $C$ can not contain only $6$ vertices as otherwise the two internal vertices must be in the same place (and the resulting graph would be $3$-colorable anyways), so $C$ contains at least $7$ vertices. A short analysis of the possible sizes of the partial wheels shows that there are exactly two possible configurations ($2$ partial wheels with $5$ vertices each, or one with $4$ and one with $6$, overlapping in one vertex), and only the second one is not $3$-colorable.