Return to Answer

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.

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).

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, 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 method, the keyword is "coset graph". (See http://www.sztaki.hu/~schneider/Teaching/4P4/chapter3.html for example).

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 this list, find all 6-valent vertex-transitive graphs on 20 vertices, filter out those which are not edge-transitive (or arc-transitive, you were not very clear) and compute their chromatic numbers!

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
Circulant
Girth 4

SsaCBLYNBOI_[?I_Ao?[??Mk@VOBZ??^_
S5x2
Non-Cayley
Girth 4

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

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

S~aKYPDHGqCQCbOWCAg_VAQ?CoGCKW?B{
S5x2 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.

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.

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.

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, 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 method, the keyword is "coset graph". (See http://www.sztaki.hu/~schneider/Teaching/4P4/chapter3.html for example).

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.

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/)

You could then simply work through this list, find all 6-valent vertex-transitive graphs on 20 vertices, filter out those which are not edge-transitive (or arc-transitive, you were not very clear) and compute their chromatic numbers!

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, 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 method, the keyword is "coset graph". (See http://www.sztaki.hu/~schneider/Teaching/4P4/chapter3.html for example).

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.

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/)

You could then simply work through this list, find all 6-valent vertex-transitive graphs on 20 vertices, filter out those which are not edge-transitive (or arc-transitive, you were not very clear) and compute their chromatic numbers!

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
Circulant
Girth 4

SsaCBLYNBOI_[?I_Ao?[??Mk@VOBZ??^_
S5x2
Non-Cayley
Girth 4

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

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

S~aKYPDHGqCQCbOWCAg_VAQ?CoGCKW?B{
S5x2 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.