Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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"

share|improve this question
    
Do you know what the genus is? –  Igor Rivin Apr 7 '12 at 1:59
    
No, the dodecahedral graph is just 3-regular (hence 30 edges) and is planar (I didn't compute "my" genus so far). The GIRTH is the SHORTEST cycle (here indeed barely 3, triangle-free would mean >3), while the diameter is the longest shortest ;-) path. –  Simon Lentner Apr 7 '12 at 17:33
    
Can you provide the adjacency matrix in some format? –  Felix Goldberg Apr 20 '12 at 9:04
    
I'll work one out as soon as possible, thanx! Which format / software-to-write would you recommend? –  Simon Lentner Apr 20 '12 at 17:02
    
Plain ascii is probably the easiest to handles, but I can handle more esoteric stuff, like g6, as well. Felix "I like writing parsers" Goldberg –  Felix Goldberg Apr 20 '12 at 18:08
add comment

5 Answers 5

up vote 14 down vote accepted

Maple's GraphTheory:-ChromaticNumber function says the chromatic number is 4. Here's one possible 4-colouring.

alt text

share|improve this answer
    
Nice, Robert! :-) –  Joseph O'Rourke Apr 7 '12 at 1:02
    
Thanks alot ... I should've though of using a computer tool ;-) If someone reongnizes, I would still be interested, if this is a "known" graph... –  Simon Lentner Apr 7 '12 at 11:46
add comment

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

share|improve this answer
    
Thanks! I'll take a look at the page you linked :-) The graphs do NOT? seem arc-transitive to me, as generall there are arcs on the icosahedron with different "geometric distance"....is that any related to Symmetry patterns in the plane (discrete subgroups of SO(2) or "Alhambra groups")? –  Simon Lentner Apr 20 '12 at 22:05
1  
Maybe the page I should have linked to is the following one : mapleta.maths.uwa.edu.au/~gordon/trans On this page, Gordon Royle has a bunch of files containing all the vertex-transitive graphs on up to 31 vertices in graph 6 format. The files are split in different categories so, if you scroll down, you will find a file containing the 80 connected 6-regular vertex-transitive graphs. It is then simply a matter of checking which are edge-transitive, etc... –  verret Apr 21 '12 at 10:26
    
As for your question, I am not sure we understand each other. A graph is arc-transitive if its automorphism group is transitive on arcs (ordered pairs of adjacent vertices). Most but not all edge- and vertex-transitive graphs are arc-transitive. I don't know about any relation to Alhambra groups but I am doubtful. –  verret Apr 21 '12 at 10:28
    
Maybe my old g6 parser will be helpful to whoever reads this thread. It's a simple matlab function I wrote back in 2007. If today there are better tools, I'll be glad to retire it. function mat=g6str2matrix(str); % Note: this only works for less than 63 vertices!!! d=double(str); n=d(1)-63; max_e=n*(n-1)/2; mat=zeros(n); Q=dec2bin(d(2:end)-63,6); W=reshape(Q',[],1)'; W=W(1:max_e); W=double(W)-48; ind=find(triu(ones(size(mat)),1)); mat(ind)=W; mat=symmetrize(mat); –  Felix Goldberg Apr 22 '12 at 10:24
    
verret, are you sure about the fourth graph? My parser stumbles on it? –  Felix Goldberg Apr 22 '12 at 10:49
show 3 more comments

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

share|improve this answer
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.