Return to Question

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 in different pentagons!).
• ...maybe you have similar ideas? I've also tried other platonic solids but these seem very sporadic cases.... ;-)

The resulting graphs are 6-regular with $1$ resp. $2$ triangles. Has anybody seen (or colored ;-) them?

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"

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"

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"...EDIT: which means the orbit of colorings under automorphisms should be large, (not only) this especially I mean with "few"

Thank you in advance for any hint :-)

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 in different pentagons!).
• ...maybe you have similar ideas? I've also tried other platonic solids but these seem very sporadic cases.... ;-)

The resulting graphs are 6-regular with $1$ resp. $2$ triangles. Has anybody seen (or colored ;-) them?

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"

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

Thank you in advance for any hint :-)

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"...EDIT: which means the orbit of colorings under automorphisms should be large, (not only) this especially I mean with "few"

Thank you in advance for any hint :-)