6
$\begingroup$

Let $G$ have order $n$ and size $m$.
Since G is planar we know $m \le 3n - 6.$ Since G is 5-regular, we know $2m = 5n$.
Using both these facts, we get that $5n \le 6n - 12$, which means $n \ge 12$. Additionally since the graph is 5-regular we know n must be even.
So far I've tried sketching 5-regular planar graphs on 12, 16, and 24 vertices, but neither of them had $\chi(G)$ = 3. I'm having trouble drawing the 5 regular planar graphs as it is, let alone finding one that is also 3-chromatic. The problem seems to be that the graphs contain too many triangles, which results in more than 3 colours being needed.
Any help for how to obtain this graph would be much appreciated.

$\endgroup$
7
$\begingroup$

The graph of the snub cuboctahedron is an example with 24 vertices:

3-colored snub cube

(drawing adapted from here; see also Mathworld for other nice drawings).

I found this by taking four copies of this fragment

                 \   \
          \   \   \   )
           \   \   \ /
        .---A---B---C----
       /   / \ / \ /
      /   /   C---A-----
     /   /   / \ /
    /   /   /   B--------
       /   /   / \
              /   `-----

and arranging them as the vertices of a tetrahedron, and it turns out the 3-coloring fits together! In the above drawing, each copy of this basic fragment is tinted green, and the faces that correspond to the faces of the original tetrahedron are tinted red.

$\endgroup$
  • $\begingroup$ Fantastic, thanks! I just kept trying to construct 5-regular planar graphs in hopes they would end up being 3-colourable, but I had no luck. I suppose I just needed to be a little more clever $\endgroup$ – SenoritaChad Nov 20 '17 at 22:58
  • 1
    $\begingroup$ @SenoritaChad: I found a name for the graph (and a nicer drawing). $\endgroup$ – Henning Makholm Nov 21 '17 at 0:56
  • 1
    $\begingroup$ This graph turns out to be the only example in Mathematica's collection of 6837 named graphs. Select[GraphData[],GraphData[#,"Planar"]&&MinMax[GraphData[#,"DegreeSequence"]]=={5,5}&&GraphData[#,"ChromaticNumber"]==3&] gives only {"SnubCubicalGraph"} as output. $\endgroup$ – Misha Lavrov Nov 30 '17 at 0:40
1
$\begingroup$

Begin with a triangle. At each vertex add three outgoing edges ($9$ in all). At each other end of these $9$ edges add four outgoing edges ($36$ in all), and so on ad infinitum. In this way on each vertex of the original triangle a tree is erected, which can be colored with two colors. Because of the basic triangle we still need three colors to color the complete graph.

$\endgroup$
  • 1
    $\begingroup$ Hmm. I wonder whether an answer with an infinite graph was envisaged ... $\endgroup$ – Henning Makholm Nov 20 '17 at 20:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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