Construct a circulant graph on 115 vertices with vertices labeled with 0 to 114. For i > j, the edge joining i and j is colored in the first color if either i - j or 115 - (i - j) is one of the following values:
1, 2, 3, 14, 15, 16, 20, 22, 23, 24
26, 28, 35, 36, 37, 39, 42, 45, 47, 49
52, 55
Otherwise the edge receives color two. There are no K5's in the first color and no K9's in the second color.
Geoff Exoo