MathCastle
Graph TheoryChallengeGraph Coloring

Graph Coloring · Challenge problem

Let GG be the graph on vertices 1,…,91,\ldots,9 where ii and jj are adjacent exactly when their difference is 11 or 22, taken cyclically mod 99 (so each vertex has degree 44; e.g. vertex 11 is adjacent to 2,3,8,92,3,8,9). What is χ(G)\chi(G)?