I'm interested in (node/edge-)symmetric 6-regular graphs on 20 vertices and 60 edges, especially ones with a A5/icosahedral/dodecahedral symmetry group and especially their chromatic number. So far I have two nonisomorphic constructions (with one resp. two triangle per edge)…both I want to identify and/or obtain a minimal coloring.
The first one has alreday been colored here, see below! (Thanks again, Robert)
Both start with the dodecahedron 1-sceleton, which is a 3-regular graph on 20 vertices. Take only the vertex set (!) and draw edges whenever…
- two vertices lay in a face pentagon and are diagonal there.
- two vertices lay in a pair of adjacient face pentagons and are connected by a short
diagonal (hence lay each in a single, distinct pentagon!). - two vertices lay in a pair of adjacient face pentagons and are connected by a long
diagonal (hence lay each in a single, distinct pentagon – note there's just a unique such diagonal in each case!). - …maybe you have similar ideas? I've also tried other platonic solids sceletons but mostly achieved planar graphs (other platonic sceletons) – these nontrivials seem very sporadic cases…. 😉
The resulting graphs are 6-regular with 1 resp. 2 triangles, the third is 5-regular with 2 triangles. Has anybody seen (or colored 😉 them? Is the shape governed by subgroups of the symmetry group?
Thank you in advance for any hint 🙂
OLD QUESTION FOR THE FIRST GRAPH. I was studying the graph, that arrises from taking vertices of a dodecahedron and connecting diagonals in any face pentagon – yielding pentagrams instead of pentagons on each face. Alternatively, it is the 1-sceleton of the "great ditrigonal icosidodecahedron"
This is a symmetric 6-regular graph with 20 vertices and hence 60 edges. There is exactly one common neighbour to each pair of adjacient vertices, so it has a girth of "barely" 3.
This must be a rather exceptional graph? But I could not find it to be named….
Especially I would like to know if the chromatic number is 4 or 5, and even if it is 4 whether one can know all (few?) such colorings ?? At least I could not find any "symmetric colorings"…which means the orbit of colorings under automorphisms should be large, (not only) this especially I mean with "few"
Best Answer
Maple's GraphTheory:-ChromaticNumber function says the chromatic number is 4. Here's one possible 4-colouring.