Graph TheoryHardGraph Coloring
Graph Coloring · Hard problem
A network of 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 others total: its two ring neighbors and its two "skip" neighbors), giving a -regular graph on an ODD number of vertices. Using the same kind of counting argument used for 's edge-coloring in this section, what is the chromatic index of this network?