The smallest 5-chromatic tournament

Bellitto, Thomas; Bousquet, Nicolas; Kabela, Adam; Pierron, Théo

doi:10.1090/mcom/3887

The smallest 5-chromatic tournament
HTML articles powered by AMS MathViewer

by Thomas Bellitto, Nicolas Bousquet, Adam Kabela and Théo Pierron;

Math. Comp. 93 (2024), 443-458

DOI: https://doi.org/10.1090/mcom/3887

Published electronically: July 11, 2023

HTML | PDF

Abstract:

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$.

References

P. Aboulker, T. Bellitto, F. Havet, and C. Rambaud, On the minimum number of arcs in $k$-dicritical oriented graphs, 2022, arXiv:2207.01051.
Jørgen Bang-Jensen, Thomas Bellitto, Thomas Schweser, and Michael Stiebitz, Hajós and Ore constructions for digraphs, Electron. J. Combin. 27 (2020), no. 1, Paper No. 1.63, 22. MR 4093164, DOI 10.37236/8942
V. Chvátal, The smallest triangle-free $4$-chromatic $4$-regular graph, J. Combinatorial Theory 9 (1970), 93–94. MR 263691, DOI 10.1016/S0021-9800(70)80057-6
Bruno Courcelle, The monadic second order logic of graphs. VI. On several representations of graphs by relational structures, Discrete Appl. Math. 54 (1994), no. 2-3, 117–149. Efficient algorithms and partial $k$-trees. MR 1300243, DOI 10.1016/0166-218X(94)90019-1
P. Erdős and L. Moser, On the representation of directed graphs as unions of orderings, Magyar Tud. Akad. Mat. Kutató Int. Közl. 9 (1964), 125–132 (English, with Russian summary). MR 168494
Paul Erdős, Problems and results in number theory and graph theory, Proceedings of the Ninth Manitoba Conference on Numerical Mathematics and Computing (Univ. Manitoba, Winnipeg, Man., 1979) Congress. Numer., XXVII, Utilitas Math., Winnipeg, MB, 1980, pp. 3–21. MR 593699
Jan Goedgebeur, On minimal triangle-free 6-chromatic graphs, J. Graph Theory 93 (2020), no. 1, 34–48. MR 4038863, DOI 10.1002/jgt.22467
Richard Hoshino and Ken-ichi Kawarabayashi, The edge density of critical digraphs, Combinatorica 35 (2015), no. 5, 619–631. MR 3437897, DOI 10.1007/s00493-014-2862-4
Tommy Jensen and Gordon F. Royle, Small graphs with chromatic number $5$: a computer search, J. Graph Theory 19 (1995), no. 1, 107–116. MR 1315429, DOI 10.1002/jgt.3190190111
Alexandr V. Kostochka and Michael Stiebitz, The minimum number of edges in 4-critical digraphs of given order, Graphs Combin. 36 (2020), no. 3, 703–718. MR 4090521, DOI 10.1007/s00373-020-02147-y
Brendan D. McKay and Adolfo Piperno, Practical graph isomorphism, II, J. Symbolic Comput. 60 (2014), 94–112. MR 3131381, DOI 10.1016/j.jsc.2013.09.003
V. Neumann Lara, The dichromatic number of a digraph, J. Combin. Theory Ser. B 33 (1982), no. 3, 265–270. MR 693366, DOI 10.1016/0095-8956(82)90046-6
V. Neumann Lara, The $3$- and $4$-dichromatic tournaments of minimum order, Discrete Math. 135 (1994), no. 1-3, 233–243. MR 1310883, DOI 10.1016/0012-365X(93)E0113-I
Víctor Neumann-Lara, Dichromatic number, circulant tournaments and Zykov sums of digraphs, Discuss. Math. Graph Theory 20 (2000), no. 2, 197–207. MR 1817491, DOI 10.7151/dmgt.1119
K. B. Reid and E. T. Parker, Disproof of a conjecture of Erdős and Moser on tournaments, J. Combinatorial Theory 9 (1970), 225–238. MR 274328, DOI 10.1016/S0021-9800(70)80061-8
Adolfo Sanchez-Flores, On tournaments free of large transitive subtournaments, Graphs Combin. 14 (1998), no. 2, 181–200. MR 1628137, DOI 10.1007/s003730050025
Neil J. A. Sloane and The OEIS Foundation Inc., The on-line encyclopedia of integer sequences, https://oeis.org/A000568.
Richard Stearns, The voting problem, Amer. Math. Monthly 66 (1959), 761–763. MR 109087, DOI 10.2307/2310461