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

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.

share|improve this question
3  
I can do 11 for coin graphs. take a coin surrounded by 6 coins and delete one outer coin. The two outer coins adjacent to the deleted coin must have the same color in a $3$-coloring. Now take two of these $6$-coin configurations, identify one of the same-color coins, and make the other two touch. Don't know if this is best possible. –  Flo Pfender Apr 2 '12 at 10:50
1  
Ok, I can do $9$ now. One can replace one of the $6$-vertex configurations above by the $4$-vertex diamond from the Moser spindle. –  Flo Pfender Apr 2 '12 at 10:56
2  
if i understand correctly, your second construction is a matchstick graph, but not a coin graph, right? –  puzzly Apr 2 '12 at 12:22
1  
oops, yes, you are correct. So I can do no better than $11$ for coin graphs. –  Flo Pfender Apr 2 '12 at 12:52
add comment

3 Answers

up vote 11 down vote accepted

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.

share|improve this answer
    
great, sounds convincing enough, except that i don't see (at least not without a bit of geometry) how |V(G)-V(C)|\geq 2 implies |V(C)|\geq 8. did u have in mind a trivial way to see that? –  puzzly Apr 3 '12 at 12:58
    
Yes, that part was a little bit hand-wavey. Fix a layout of a coin graph containing a cycle C and two additional vertices contained in the disc bounded by C. Let C' be the piecewise linear curve in the plane defined by the center of the coins of V(C). We may assume that the disc bounded by C' is convex, and so we may assume the two coins not in C are touching. If we place 8 coins around the interior pair of coins as tightly as possible, we see there exists a curve C'' of length 8 contained in the disc bounded by C'. Thus, C' has length at least 8, and if exactly 8 then C' = C'' –  Paul Wollan Apr 3 '12 at 15:28
1  
well $C''$ is not unique. Notice that you can shift the $8$ coins around the two middle coins a bit, so that either both middle coins have degree $4$, or both have degree $5$. But I do think that your proof shows that the $11$-coin configuration is unique. $3$ internal vertices would require a $9$-cycle, and there are only two ways an induced $9$-cycle can have each vertex touch at least one of the two central vertices, and one of these ways is $3$-colorable. –  Flo Pfender Apr 3 '12 at 16:28
    
Thanks Flo, that's right. So, the final claim in the proof that we must be equal to two adjacent vertices x and y each adjacent to five of the boundary vertices was not correct. I fixed the proof above. –  Paul Wollan Apr 4 '12 at 14:31
add comment

Here is Flo Pfender's 11-coin graph:
           Coin Graph

share|improve this answer
add comment

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.

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.