I have generated a single random 17th degree 100 vertex graph, with self-loops and multiple edges rerandomized out of existence, so the graph is highly 17 regular, and after long computation with a satisfiability solver, generated a 6 coloring. The graph and its coloring are available by email.
Presently, my three new (tight) claims are:
Almost all 9 regular graphs are 4 colorable. (many random examples)
Almost all 13 regular graphs are 5 colorable. (some random examples)
Almost all 17 regular graphs are 6 colorable. (one random example)
(Almost all 5 regular graphs are 3 colorable is well known, the others are new.)
The tightness of theorem 1.1 means these graphs are very difficult to k-color. I would like to know when the increment by 4 in the degree will fail with the increment in number of colors, for future work.
Main question: Is the single successful randomly generated 17 regular graph at some number of vertices (100) sufficient to prove the almost all 6 colorability claim?
Second question: Does the result help improve the error terms in the previously cited paper (theorem 1.1 of the paper, "On the chromatic number of random regular graphs.")? I want to predict whether 21 regular graphs are worth exploring for 7 colorings...