9
$\begingroup$

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"

Improve this question
$\endgroup$
5
  • $\begingroup$ Do you know what the genus is? $\endgroup$
    – Igor Rivin
    Commented Apr 7, 2012 at 1:59
  • $\begingroup$ 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. $\endgroup$
    – Simon Lentner
    Commented Apr 7, 2012 at 17:33
  • $\begingroup$ Can you provide the adjacency matrix in some format? $\endgroup$
    – Felix Goldberg
    Commented Apr 20, 2012 at 9:04
  • $\begingroup$ I'll work one out as soon as possible, thanx! Which format / software-to-write would you recommend? $\endgroup$
    – Simon Lentner
    Commented Apr 20, 2012 at 17:02
  • $\begingroup$ 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 $\endgroup$
    – Felix Goldberg
    Commented Apr 20, 2012 at 18:08

5 Answers 5

Reset to default
18
$\begingroup$

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

alt text

Improve this answer
$\endgroup$
2
  • $\begingroup$ Nice, Robert! :-) $\endgroup$
    – Joseph O'Rourke
    Commented Apr 7, 2012 at 1:02
  • $\begingroup$ 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... $\endgroup$
    – Simon Lentner
    Commented Apr 7, 2012 at 11:46
10
$\begingroup$

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

Improve this answer
$\endgroup$
8
  • $\begingroup$ 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")? $\endgroup$
    – Simon Lentner
    Commented Apr 20, 2012 at 22:05
  • 1
    $\begingroup$ 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... $\endgroup$
    – verret
    Commented Apr 21, 2012 at 10:26
  • $\begingroup$ 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. $\endgroup$
    – verret
    Commented Apr 21, 2012 at 10:28
  • $\begingroup$ 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); $\endgroup$
    – Felix Goldberg
    Commented Apr 22, 2012 at 10:24
  • $\begingroup$ verret, are you sure about the fourth graph? My parser stumbles on it? $\endgroup$
    – Felix Goldberg
    Commented Apr 22, 2012 at 10:49
2
$\begingroup$

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

Improve this answer
$\endgroup$
2
$\begingroup$

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

Improve this answer
$\endgroup$
2
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .