论文标题
最小的5色锦标赛
The smallest 5-chromatic tournament
论文作者
论文摘要
Digraph的着色是其顶点集的分区，因此每个类都不会导致无向周期的挖掘物。如果$ k $是该分区中的最低类，则digraph为$ k $ - 奇异，并且如果每对顶点之间最多有一个弧线，则将挖掘者定向。显然，最小的$ k $ chromation Digraph是$ K $顶点的完整挖掘物，但是确定最小的$ k $ chromatic图形的顺序是一个具有挑战性的问题。众所周知，最小的$ 2 $ - ，$ 3 $ - 和$ 4 $ - 面向冠的图形分别具有$ 3 $，$ 7 $和$ 11 $的顶点。 1994年，诺伊曼·拉拉（Neumann-Lara）猜想，最小的$ 5 $ chronic graph具有$ 17 $的顶点。我们解决了这个猜想，并表明正确的订单为$ 19 $。
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$.
