12
$\begingroup$

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.

$\endgroup$
4
  • 4
    $\begingroup$ 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. $\endgroup$ Apr 2, 2012 at 10:50
  • 1
    $\begingroup$ 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. $\endgroup$ Apr 2, 2012 at 10:56
  • 2
    $\begingroup$ if i understand correctly, your second construction is a matchstick graph, but not a coin graph, right? $\endgroup$
    – puzzly
    Apr 2, 2012 at 12:22
  • 1
    $\begingroup$ oops, yes, you are correct. So I can do no better than $11$ for coin graphs. $\endgroup$ Apr 2, 2012 at 12:52

3 Answers 3

13
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$
    – puzzly
    Apr 3, 2012 at 12:58
  • $\begingroup$ 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'' $\endgroup$ Apr 3, 2012 at 15:28
  • 1
    $\begingroup$ 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. $\endgroup$ Apr 3, 2012 at 16:28
  • $\begingroup$ 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. $\endgroup$ Apr 4, 2012 at 14:31
10
$\begingroup$

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


           Coin Graph


$\endgroup$
3
  • 2
    $\begingroup$ Also shown on Wikipedia with actual coins: commons.wikimedia.org/wiki/File:Penny_graph.jpg $\endgroup$ Sep 6, 2017 at 21:50
  • $\begingroup$ @DavidEppstein: Ha! (But they're not colored. :-)) $\endgroup$ Sep 6, 2017 at 22:56
  • 3
    $\begingroup$ True, but the interesting aspect of this graph is not that it can be 4-colored (that's true and easy for all penny graphs) but that it cannot be 3-colored. And I don't know how to show that visually so easily. $\endgroup$ Sep 7, 2017 at 1:19
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.