How can we prove that a coin graph is 4-colorable???Also, can we find any example of an non-3-colorable coin graph.
$\begingroup$
$\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$– Noah SchweberSep 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$– Johannes HahnSep 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$– Noah SchweberSep 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$– Johannes HahnSep 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$– Noah SchweberSep 18, 2014 at 2:34
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.