Circular colored graph, minimum of colors needed
Source: Latvian TST for Baltic Way 2022 P7
November 25, 2022
combinatoricsgraph theory
Problem Statement
A kingdom has towns. All of the towns lie on a circle, and there is a one-way road going from every town to the next towns in a clockwise order. Each road is colored in one color. Additionally, it is known that for any ordered pair of towns and it is possible to find a path from to so that no two roads of the path would have the same color. Find the minimal number of road colors in the kingdom.