# What is the smallest 4-chromatic graph of girth 5?

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.

• It is on at least 15 vertices.
– joro
Jan 12, 2015 at 10:34
• @joro can you give more details? Jan 13, 2015 at 9:14
• 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).
– joro
Jan 13, 2015 at 9:16
• Here it is: gist.github.com/jor0/e2402a8dfb3a210dc88d#file-mogirth5-sage Probably comment the suggested printing for speed.
– joro
Jan 13, 2015 at 9:33
• 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$. Jan 13, 2015 at 13:44

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_?kPCGcOFCG?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;


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

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_?kPCGcOFCG?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?Cc@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?WA_D?@_CGSCc?@J?JH?pcEAK?t?_
T???C@?GC_H?@_T??[BCOAIac_CSa@aK?C[_
`
• Did you use nauty for graph generation? How long the generation took?
– joro
Jan 15, 2015 at 6:39
• 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. Jan 15, 2015 at 6:48
• So 21 is the answer then? Is the Brinkman graph the unique 4-chromatic graph of girth 5 and order 21? Jan 15, 2015 at 6:55
• @verret Assuming correctness of computations the answer is 21.
– joro
Jan 15, 2015 at 7:00
• @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. Jan 15, 2015 at 7:01

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.

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