show/hide this revision's text 4 added 330 characters in body; added 21 characters in body

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).
show/hide this revision's text 3 deleted 836 characters in body; deleted 3 characters in body

If you are interested in constructing all 6-regular graphs on 20 vertices admitting a A5/icosahedral/dodecahedral vertex-transitive symmetry group, there is a very natural way to do this.

Let's take $G=A_5$ for example. Since $G$ will act faithfully and transitively on the 20 vertices, its action will be equivalent to the action of $G$ on the cosets of a subgroup of order 3. (This is a basic fact in permutation group theory).

Up to conjugacy, there is only one class of subgroups of order 3 in $G$, hence,

EDIT : Cleaned up to equivalence, there is only one transitive action of $G$ on 20 points. Now, to reconstruct all the 6-regular graphs, all you have to do is find a set of sub-orbits with total size 6 and which is closed under "pairing". In fact, if you want $G$ to act arc-transitively, then you need to find a self-paired sub-orbit of length 6.

The same method can be applied to the icosahedral\dodecahedral groups.

If you are not familiar with this methodanswer, the keyword is "coset graph".(See http://www.sztaki.hu/~schneider/Teaching/4P4/chapter3.html for example)added more info.

Moreover,

20 is small enough that , with a little more work, it is possible to find ALL the symmetric 6-valent graphs on 20 vertices.

You could then simply work through

On this list, find page:

mapleta.maths.uwa.edu.au/~gordon/trans

Gordon Royle has a bunch of files containing all 6-valent the vertex-transitive graphs on 20 up to 31 vertices , filter out those which in graph6 format. The files are not edge-transitive (or arc-transitivesplit in different categories so, if you were not very clear) and compute their chromatic numbers!

EDIT:scroll down, you will find a file containing the connected 6-regular vertex-transitive graphs.

One of them is a Circulantcirculant, three are Cayley graphs on F20 (the Frobenius group of order 20) and the last one is not a Cayley graph. They all have girth 3 or 4.I was only able to compute

Here is some info about the chromatic number in one casegraphs.

Here they are in graph6 format, with a summary of The first line is the graph6 data . (I can post the adjacency matrices if you prefer thatthat), the second line is a rough description of the automorphism group.The other lines should be self-explanatory.

Chromatic number 3

Chromatic number 2

2^10:S5,

S{aSQGGhI?oE@OpGc_eIAgROgXQ_B{?
Chromatic number 3

S{aSQ`GGhI?oE@OpGc`_eIAgROgXQ_B{?
Chromatic number 4

Chromatic Number number 4.

The second line is a rough description of the automorphism

For group calculations, I used Magma. For chromatic numbers, I used Sage. The first one has a solvable group, so will not have contain the groups you are interested in. All the others contain copies of A5.
show/hide this revision's text 2 added 1137 characters in body; added 37 characters in body; added 1 characters in body

EDIT: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. They all have girth 3 or 4. I was only able to compute the chromatic number in one case.

Here they are in graph6 format, with a summary of the data. I can post the adjacency matrices if you prefer that.

SsaCBLYNAWEOP@Q@@_`CRCagoJ?Bf?B_w
(10x2):D6
Girth 4

SsaCBLYNBOI_[?I_Ao?[??Mk@VOBZ??^_
Girth 4

SsaCB|_WB?K?EKEKB@_oW@kKEooK]?K]?
2^10:S5, Cayley on F20
Girth 4

S{aSQGGhI?oE@OpGc_eIAgROgXQ_B{?
Cayley on F20
Girth 3

S~aKYPDHGqCQCbOWCAg_VAQ?CoGCKW?B{
Cayley on F20
Girth 3
Chromatic Number 4.

The second line is a rough description of the automorphism group. The first one has a solvable group, so will not have the groups you are interested in. All the others contain copies of A5.
show/hide this revision's text 1