0
$\begingroup$

How can we prove that a coin graph is 4-colorable???Also, can we find any example of an non-3-colorable coin graph.

$\endgroup$
5
  • 3
    $\begingroup$ See mathoverflow.net/questions/92883/small-4-chromatic-coin-graphs for examples of non-3-colorable coin graphs. As to your first question, every coin graph is planar . . . $\endgroup$ Sep 17, 2014 at 21:26
  • $\begingroup$ Also: The picture on en.wikipedia.org/wiki/Coin_graph is non-3-colorable... This page also clearly states that your question is equivalent to the four-color-problem. This does not show much effort on your side... $\endgroup$ Sep 17, 2014 at 22:49
  • $\begingroup$ @JohannesHahn, your second point is not correct: coin graphs are circle packings where each circle is required to have radius 1. So, in particular, "every coin graph is four-colorable" is not equivalent to the four color theorem. In fact, the question I linked to says that "it's easy to show by induction" that every coin graph is four-colorable. $\endgroup$ Sep 17, 2014 at 23:17
  • $\begingroup$ @NoahS That's not the definition of "coin graph" wikipedia uses. Is this some sort of standard terminology that is used in the wrong way? (I'm not a graph theorist and haven't heard of coin graphs at all before this question) $\endgroup$ Sep 17, 2014 at 23:47
  • $\begingroup$ I was going by the definition in the linked question. (I'm not a graph theorist either :P) Seems there is ambiguity there. $\endgroup$ Sep 18, 2014 at 2:34

1 Answer 1

7
$\begingroup$

The phrase "coin graph" sometimes requires equal coins and sometimes allows non-equal coins. I am assuming the former meaning as indicated in the comments: equal coins.

This paper says that the 4-colourability can be proved using a "simple induction". I'll try: Consider the convex hull of the coin centres. A coin whose centre is a vertex of the convex hull is adjacent to at most 3 other coins, so you can always colour it after you colour the others.

Finally, the example shown in Fig 1 of that paper is not 3-colourable.

$\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.