11
$\begingroup$

It is known that the smallest 4-chromatic graph of girth 4 is the Grötzsch graph (11 vertices). What happens for girth 5?

The Brinkmann graph (21 vertices) has chromatic number 4, girth 5 and is 4-regular. Moreover it is the smallest graph (in terms of the order) with these three properties.

Dropping the 4-regularity constraint, is there a graph of smaller order than the Brinkmann graph that is 4-chromatic and of girth 5? I haven't found anything in the literature but I may have missed it.

$\endgroup$
  • $\begingroup$ It is on at least 15 vertices. $\endgroup$ – joro Jan 12 '15 at 10:34
  • $\begingroup$ @joro can you give more details? $\endgroup$ – Florent Foucaud Jan 13 '15 at 9:14
  • $\begingroup$ I did computer search in sage. Let me know if you need the code to run it longer if you wish (I gave up in about 15 minutes). $\endgroup$ – joro Jan 13 '15 at 9:16
  • 1
    $\begingroup$ Here it is: gist.github.com/jor0/e2402a8dfb3a210dc88d#file-mogirth5-sage Probably comment the suggested printing for speed. $\endgroup$ – joro Jan 13 '15 at 9:33
  • 4
    $\begingroup$ Since $\delta\geq 3$, we may estimate $\Delta$ better. Take any vertex of degree $\Delta$; all its $\Delta$ neighbors, as well as their $\geq (\delta-1)\Delta$ other neighbors are distinct (due to the girth condition), so there are at least $1+\Delta\delta$ vertices at all. Thus, if $\Delta\geq 7$ then there are at least 22 vertices, and we may assume $\Delta\leq 6$. $\endgroup$ – Ilya Bogdanov Jan 13 '15 at 13:44
9
$\begingroup$

My computer tells me that there 195291625 graphs on 20 vertices with minimum degree at least 3 and maximum degree at most 6 and girth at least 5.

Sadly none of them have chromatic number 4, I just get 48 bipartite ones and the remainder being 3-chromatic.

Independent verification would be useful.

Added Here's a 21-vertex graph that is not the Brinkmann graph, but is 4-chromatic and has girth equal to 5, also in graph6 format for direct input to Sage. It has the same number of edges as a 4-regular graph but has two vertices of degree 3 and two of degree 5. I bet that it is obtained from the Brinkmann graph by some small edge-swap move.

g = Graph("T???C@?K@OA_A_b?AWAQ_?kPCGc`OFCG?da?")

Graph 1, order 21.
  0 : 7 13 18 19;
  1 : 8 15 17 19;
  2 : 9 10 19 20;
  3 : 9 11 14 18;
  4 : 10 12 13 15;
  5 : 11 13 17 20;
  6 : 12 14 16 19;
  7 : 0 14 15 20;
  8 : 1 16 18 20;
  9 : 2 3 15 16;
 10 : 2 4 17 18;
 11 : 3 5 19;
 12 : 4 6 20;
 13 : 0 4 5 16;
 14 : 3 6 7 17;
 15 : 1 4 7 9;
 16 : 6 8 9 13;
 17 : 1 5 10 14;
 18 : 0 3 8 10;
 19 : 0 1 2 6 11;
 20 : 2 5 7 8 12;

More added

There are smaller 4-chromatic girth-5 graphs than Brinkmann's graph, because some of the examples that are appearing have fewer edges even though they have the same number of vertices. The search is about 10% complete and there are 7 graphs found so far.

The prettiest one has just 40 edges and an automorphism group of order 5 consisting of a single fixed point and 4 5-cycles (which is vaguely reminiscent of Mycielski's construction).

Final Addition

After a little over 31 hours on the same multi-core machine, the computation of the full list of graphs with minimum degree at least 3, maximum degree at most 6 and girth at least 5 terminated.

Of the 5006797077 graphs constructed, just 18 had chromatic number 4 and therefore have an equal claim to being the smallest 4-chromatic graphs of girth 5 (at least in terms of counting vertices).

Among these graphs, 1 has 40 edges, 3 have 41, 12 have 42 and 2 have 43 edges. One is the 4-regular Brinkmann graph. The automorphism groups have orders 14 (Brinkmann graph), 5 (the element of order 5 has one fixed point and 4 x 5-cycles), 2 (8 times) and 1 (8 times). Some of the graphs are obtained from the others by adding/deleting an edge, but mostly not.

For those interested, the graphs (in graph6 format) are as follows:

T???C@?K@OA_A_b?AWAQ_?kPCGc`OFCG?da?
T???C@?GC_B?@_p?@W@cADS@`CCDg@HP@GY?
T???C@?GC_B?@_p??T@cAOp?Po@Y@AOsA_e?
T???C@?GC_B?@_p??T@cAAE_SoAEgD@K?l?_
T???C@?GC_B?@_p??T@cAAE_So@Q@AEGA_e?
T???C@?GC_B?@_p??T@cAAE_So@Q@AEgA_e?
T???C@?GC_B?@_b?@WAIGCWaac?HpBOS@QP?
T????A?OD?B?P_[?Ac@W?@F?I`@BKAQPAROO
T????A?O@?Q?F?S_HC@S?HGQGWFAC?b__FK_
T???C@?g?o?os?PCKP?d_AoOpCCPG@WC?Dg?
T???C@?G?oA_A__`IGB?QH?jK?C`c@RG?FW?
T???C@?GC_@_E_QOOS?M?CX?s@_PobCWBCQ?
T????A?O@_@_g_Y?BC?H_CD_R@QDWCQo@DA_
T???C@?G?_P?R?IOOa?i?SDAqAACR?T__ck?
T????A?O@?Q?R?[?BO@P?AF?E`?bSAEGadO_
T????A?O@?Q?R?[?BO@P?AF?E`GbSAEGadO_
T????A?WA_D?@_`CGSCc?@J?JH?pcEAK?t?_
T???C@?GC_H?@_T??[BCOAIac_CSa@aK?C[_
$\endgroup$
  • $\begingroup$ Did you use nauty for graph generation? How long the generation took? $\endgroup$ – joro Jan 15 '15 at 6:39
  • 2
    $\begingroup$ 1000 small processes, each of the form geng -t -f -d3 -D6 20 x/1000 (where x ranges from 0..999) run in parallel on a machine with 2 cpus, each with 6 cores, each with 2 threads. Total elapsed time was about 2 hours. $\endgroup$ – Gordon Royle Jan 15 '15 at 6:48
  • $\begingroup$ So 21 is the answer then? Is the Brinkman graph the unique 4-chromatic graph of girth 5 and order 21? $\endgroup$ – verret Jan 15 '15 at 6:55
  • $\begingroup$ @verret Assuming correctness of computations the answer is 21. $\endgroup$ – joro Jan 15 '15 at 7:00
  • 3
    $\begingroup$ @joro My meta-algorithm for all graph isomorphism or computation problems is: (1) Check whether any program in the nauty package (nauty, Traces, geng, genbg, plantri, etc) does exactly what I want, (2) Check whether I can write a plug-in to any of the above that does what I want, (3) Ask Brendan if he's got a non-distributed program that does what I want, (4) Write the damn thing myself. $\endgroup$ – Gordon Royle Jan 15 '15 at 7:01
3
$\begingroup$

Partial answer based on computer search.

There is no smaller solution with $\delta \ge 4$.

According to comments, smaller graph must satisfy $\delta \ge 3, \Delta \le 6$.

If it is exists, it is on $20$ vertices.

Link to sage implementation is in the comments.

$\endgroup$
  • $\begingroup$ I'm running the program, it has n't found any with 19 vertices. $\endgroup$ – Florent Foucaud Jan 14 '15 at 7:55
  • $\begingroup$ @FlorentFoucaud I suppose you applied the patch "-d3 -D6"? Did you finish all of order 19? $\endgroup$ – joro Jan 14 '15 at 8:07
  • $\begingroup$ @FlorentFoucaud I finished order 19, no solutions. $\endgroup$ – joro Jan 14 '15 at 10:51
  • $\begingroup$ Yes this is what I meant too in my earlier comment. $\endgroup$ – Florent Foucaud Jan 14 '15 at 15:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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