Cfrgtkky

***EDIT

The graph given below was indeed the smallest at the time of writing, but in the meantime smaller examples have been found (one with 40 vertices can be found here)

The supporting "theorem" turned out to be incorrect (at least without additional conditions). The proof in mentioned article of Jensen and Royle has the same error.

*** END EDIT

Jensen and Royle (in "Small graphs with chromatic number 5: A computer search" (*))
provide an easy construction of a 22-vertex graph (from the Grötzsch graph)
and an easy proof that the result is triangle-free and 5-chromatic.

Applying the Mycielski construction to this graph gives a 45-vertex, triangle-free, 6-chromatic graph.
Chartrand and Zhang (on page 162 of their book "Chromatic Graph Theory") say that it is unknown
if a smaller such graph exists.

A close inspection of the proof in paper (*) shows that their construction
and the proof is really just one instance of a more general construction and theorem:

Theorem:
Let $G$ be a triangle-free $k$-chromatic graph on $n$ vertices and $S$ an independent set of size $t$ with $t<k$
such that no ($k-2$)-coloring of the non-neighbours of $S$ can be extended to a $k-1$-coloring
of $G-S$, then there is a triangle-free ($k+1$)-chromatic graph $G'$ on $2n+2-t$ vertices.

Both the proof and the construction can be transferred from (*) almost verbatim
("almost" because the paper finds a graph that has one edge less than the general construction:
if they would have added that edge their proof would have been even simpler).

Note: applying the theorem with $G=C_5$, $k=3$ and $t=1$ leads to an alternative construction
of the Grötzsch graph.

Note: applying the theorem with $G$ being the Grötzsch graph, $k=4$ and $t=2$ (and an appropriate choice of $S$)
leads to the graph from paper (*) with one extra edge. We call this $G_{22}$.

Now it turns out to be very easy (for a computer) to find two independent vertices
in $G_{22}$ that satisfy the conditions for the theorem, so this leads to a triangle-free,
6-chromatic graph with 44 vertices.

I have not yet tried if there are larger independent sets that satisfy the conditions
for the theorem (which would lead to even smaller graphs). I am not even sure
if an exhaustive search is feasible.

Now I have three questions.

Question 1: Is it still true that 45 vertices is the current record?

Question 2: Is anyone able to provide an independent verification that the graph
defined below is indeed 6-chromatic. I do not doubt the theorem, but the used software
is home-brewn so it may contain an error.
The graph is provided as a Sage definition but I can provide any other format
if I have a description of that format.
Sage already tells me that it indeed is triangle-free, but the server throws me out
before it has verified that the graph is not 5-colorable.
This is not too bad: failure attempts with 44-vertex graphs that actually were
5-colorable, quickly returned. The fact that this one takes long is a good indication
that it indeed is NOT 5-colorable.

Question 3: The theorem is rather general, but the provided example will probably be
its only practical use: finding independent sets that satisfy the conditions in graphs
with approximately 40 vertices (which would be the next step) does not seem realistic
with current computer speed. So, does it make sense to make this result more "official"?
And, if yes, I could use a person who guides me in that process.

g=Graph()

g.add_vertices(

 [0,1,2,3,4,5,6,7,8,9

 ,10,11,12,13,14,15,16,17,18,19

 ,20,21,22,23,24,25,26,27,28,29

 ,30,31,32,33,34,35,36,37,38,39

 ,40,41,42,43])

g.add_edges(

 [(0,1),(0,4),(0,6),(0,9),(0,13),(0,16),(0,22),(0,23),(0,26),(0,27)

 ,(0,30),(0,34),(0,37),(1,2),(1,5),(1,7),(1,12),(1,14),(1,17),(1,18)

 ,(1,24),(1,28),(1,33),(1,35),(1,38),(1,39),(2,3),(2,6),(2,8),(2,13)

 ,(2,15),(2,19),(2,23),(2,25),(2,27),(2,29),(2,34),(2,36),(2,40),(3,4)

 ,(3,7),(3,9),(3,14),(3,16),(3,18),(3,24),(3,26),(3,28),(3,30),(3,35)

 ,(3,37),(3,39),(4,5),(4,8),(4,12),(4,15),(4,17),(4,19),(4,25),(4,29)

 ,(4,33),(4,36),(4,38),(4,40),(5,10),(5,13),(5,16),(5,20),(5,22),(5,23)

 ,(5,26),(5,31),(5,34),(5,37),(5,41),(6,10),(6,11),(6,12),(6,14),(6,20)

 ,(6,24),(6,31),(6,32),(6,33),(6,35),(6,41),(7,10),(7,13),(7,15),(7,20)

 ,(7,23),(7,25),(7,31),(7,34),(7,36),(7,41),(8,10),(8,14),(8,16),(8,20)

 ,(8,24),(8,26),(8,31),(8,35),(8,37),(8,41),(9,10),(9,11),(9,12),(9,15)

 ,(9,20),(9,25),(9,31),(9,32),(9,33),(9,36),(9,41),(10,17),(10,18),(10,19)

 ,(10,27),(10,28),(10,29),(10,30),(10,38),(10,39),(10,40),(11,13),(11,16),(11,17)

 ,(11,18),(11,19),(11,27),(11,30),(11,34),(11,37),(11,38),(11,39),(11,40),(12,21)

 ,(12,23),(12,26),(12,27),(12,30),(12,42),(13,21),(13,24),(13,28),(13,32),(13,42)

 ,(14,21),(14,23),(14,25),(14,27),(14,29),(14,42),(15,21),(15,24),(15,26),(15,28)

 ,(15,30),(15,42),(16,21),(16,25),(16,29),(16,32),(16,42),(17,21),(17,23),(17,26)

 ,(17,31),(17,32),(17,42),(18,21),(18,23),(18,25),(18,31),(18,32),(18,42),(19,21)

 ,(19,24),(19,26),(19,31),(19,32),(19,42),(20,21),(20,27),(20,28),(20,29),(20,30)

 ,(20,42),(21,33),(21,34),(21,35),(21,36),(21,37),(21,38),(21,39),(21,40),(21,41)

 ,(22,24),(22,25),(22,28),(22,29),(22,32),(22,33),(22,35),(22,36),(22,38),(22,39)

 ,(22,40),(22,42),(23,43),(24,43),(25,43),(26,43),(27,43),(28,43),(29,43),(30,43)

 ,(31,43),(32,43),(33,43),(34,43),(35,43),(36,43),(37,43),(38,43),(39,43),(40,43)

 ,(41,43),(42,43)])

As far as representing graphs goes, I think the best way is to give its graph6 string representation, which for this case would be...

khdLA_gc?N_QQchPIS@Q_dH@GKA_W@OW?Fo???~{G??SgSoSgSQISIaQcQgD?@?SASI?gGggC_[`??N_M??APNG?Qc?E?DIG?_?IS?B??IS?E??dH?C??H@_B??A_W?o??IB?E???Fo?O????F~O??????N~~{

...and works well within Sage.

With regards to the chromatic number I can confirm it is indeed 6. The result was obtained by solving the linked linear program with CPLEX with the switch CPX_MIPEMPHASIS_BESTBOUND. The check took ~200s.

As far as the other questions, I think that at least one of the authors of the mentioned papers hangs around here and may jump in to answer.

As far as I know, nobody has published or made available any triangle-free 6-chromatic graph on fewer than 45 vertices, so this is the record-holder.

Is this worth publishing? Personally, I would put it on arxiv immediately to establish your priority, but then keep working on it to see if you can derive any consequences or find more examples etc. before writing it up as a formal paper.