MathCastle
Graph TheoryHardGraph Coloring

Graph Coloring · Hard problem

Let C7C_7 be the 77-cycle on vertices 1,…,71,\ldots,7 with edges 12,23,34,45,56,67,7112,23,34,45,56,67,71. Let GG be the COMPLEMENT of C7C_7: two vertices are adjacent in GG exactly when they are NOT adjacent in C7C_7 (and are not the same vertex). What is χ(G)\chi(G)?