Highly symmetric 6-regular graph with 20 vertices 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"
 A: Okay, I think I can show that $\chi \leq 5$ for the second graph on verret's list.
Using Iglin's wonderful matlab package for graph theory (http://www.mathworks.com/matlabcentral/fileexchange/4266) I found out that its independence number is $\alpha=10$.
In a recent paper (http://www.sciencedirect.com/science/article/pii/S0012365X09002842) Kohl & Schiermeyer have shown that Reed's conjecture holds for graphs with $\Delta \geq n - \alpha -4$. 
QED
A: Now I realized that I can just run S.Iglin's graph coloring function for the five graphs. The results are:
3     2     3     4     4
A: I just found one of these graphs. It is constructed  as follows:
In $A_5$, let $C$ be the class with $20$ elements and let $C$ be the vertex set. An edge is a pair $(x,y)$ where $xy \in C$. Then there are $60$ edges. Call the graph $G$.
Then $\operatorname{Aut}(G)$ is $C_2 x S_5$; $G$ has girth $3$, degree $6$, and chromatic number $4$. It is vertex- and edge-transitive.
A: Maple's GraphTheory:-ChromaticNumber function says the chromatic number is 4.  Here's one possible 4-colouring.

A: EDIT : Cleaned up answer, added more info.
20 is small enough that it is possible to find ALL the symmetric 6-valent graphs on 20 vertices.
In fact, all the vertex-transitive graphs up to 32 vertices of any valency are known!
(See http://symomega.wordpress.com/2012/02/27/there-are-677402-vertex-transitive-graphs-on-32-vertices/)
On this page:
mapleta.maths.uwa.edu.au/~gordon/trans
Gordon Royle has a bunch of files containing all the vertex-transitive graphs on up to 31 vertices in graph6 format. The files are split in different categories so, if you scroll down, you will find a file containing the connected 6-regular vertex-transitive graphs. 
I went ahead and checked Gordon's data. Out of the 80 connected 6-valent vertex-transitive graphs on 20 vertices, only 5 are also edge-transitive. (They are also arc-transitive).
One of them is a circulant, three are Cayley graphs on F20 (the Frobenius group of order 20) and the last one is not a Cayley graph.
Here is some info about the graphs.
The first line is the graph6 data (I can post the adjacency matrices if you prefer that), the second line is a rough description of the automorphism group.
The other lines should be self-explanatory.
SsaCBLYNAWEOP@Q@@_`CRCagoJ?Bf?B_w
(10x2):D6
Circulant
Girth 4
Chromatic number 3
SsaCBLYNBOI_[?I_Ao?[??Mk@VOBZ??^_
S5x2
Non-Cayley
Girth 4
Chromatic number 2
SsaCB|_WB?K?EKEKB@_oW@kKEooK]?K]?
2^10:S5
Cayley on F20
Girth 4
Chromatic number 3
S{aSQ`GGhI?oE@OpGc`_eIAgROgXQ_B{?
S5x2
Cayley on F20
Girth 3
Chromatic number 4
S~aKYPDHGqCQCbOWCAg_VAQ?CoGCKW?B{
S5x2
Cayley on F20
Girth 3
Chromatic number 4.
For group calculations, I used Magma. For chromatic numbers, I used Sage. The first one has a solvable group, so will not contain the groups you are interested in. All the others contain copies of A5.
The graph that was already colored by Robert should be one of those two last ones.
Just looking at the data, my guess is that the second one is the canonical double cover of the complement of the Petersen graph, while the third one is the lexicographic product of the Petersen graph with an edgeless graph on 2 vertices (I didn't actually check).
