MathCastle
Graph TheoryHardGraph Coloring

Graph Coloring · Hard problem

A network of 77 machines is arranged in a ring, and EVERY machine is also directly linked to the two machines two positions away (so each machine links to 44 others total: its two ring neighbors and its two "skip" neighbors), giving a 44-regular graph on an ODD number of vertices. Using the same kind of counting argument used for K5K_5's edge-coloring in this section, what is the chromatic index of this network?