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"