The arcs of a circle represent the vertex sets of circular graphs: “Two vertices are adjacent if and only if their corresponding arcs intersect.” A circular graph is proper if no arc representing a vertex is contained properly in another arc representing a vertex.

Hadwiger’s conjecture states that if the chromatic number of a graph G equals r, then the complete graph on r vertices is a minor of G. This paper addresses Hadwiger’s conjecture for proper circular graphs. In a series of lemmas, it is shown that this “conjecture is true for proper circular arc graphs.”

The proof uses clever combinatorial arguments. Proving this conjecture for the class of proper circular graphs is important on its own, but circular graphs are also important mathematical objects with many applications--for example, in statistics and computer science (CS).