The smallest 5-chromatic tournament

10/18/2022
by   Thomas Bellitto, et al.
0

A coloring of a digraph is a partition of its vertex set such that each class induces a digraph with no directed cycles. A digraph is k-chromatic if k is the minimum number of classes in such partition, and a digraph is oriented if there is at most one arc between each pair of vertices. Clearly, the smallest k-chromatic digraph is the complete digraph on k vertices, but determining the order of the smallest k-chromatic oriented graphs is a challenging problem. It is known that the smallest 2-, 3- and 4-chromatic oriented graphs have 3, 7 and 11 vertices, respectively. In 1994, Neumann-Lara conjectured that a smallest 5-chromatic oriented graph has 17 vertices. We solve this conjecture and show that the correct order is 19.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset