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 K_{5}'s in the first color and
no K_{9}'s in the second color.

Geoff Exoo