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
Bibliographic Information
- Thomas Bellitto
- Affiliation: Faculty of Mathematics, Informatics and Mechanics, University of Warsaw, Poland
- Address at time of publication: Sorbonne Université, CNRS, LIP6, F-75005 Paris, France
- MR Author ID: 1256268
- ORCID: 0009-0001-5424-0742
- Email: thomas.bellitto@lip6.fr
- Nicolas Bousquet
- Affiliation: Univ. Lyon, Université Lyon 1, LIRIS UMR CNRS 5205, F-69621 Lyon, France
- MR Author ID: 949589
- ORCID: 0000-0003-0170-0503
- Email: nicolas.bousquet@univ-lyon1.fr
- Adam Kabela
- Affiliation: Faculty of Informatics, Masaryk University, Brno, Czech Republic
- Address at time of publication: Faculty of Applied Sciences, University of West Bohemia, Pilsen, Czech Republic
- MR Author ID: 1187261
- Email: kabela@kma.zcu.cz
- Théo Pierron
- Affiliation: Faculty of Informatics, Masaryk University, Brno, Czech Republic
- Address at time of publication: Univ. Lyon, Université Lyon 1, LIRIS UMR CNRS 5205, F-69621 Lyon, France
- Email: theo.pierron@univ-lyon1.fr
- Received by editor(s): October 18, 2022
- Received by editor(s) in revised form: April 7, 2023
- Published electronically: July 11, 2023
- Additional Notes: The first author was supported by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme Grant Agreement 714704. The second and fourth authors were supported by the ANR project GrR (ANR-18-CE40-0032). The third and fourth authors were supported by the MUNI Award in Science and Humanities of the Grant Agency of Masaryk University. The third author was also supported by project GA20-09525S of the Czech Science Foundation.
- © Copyright 2023 by the authors
- Journal: Math. Comp. 93 (2024), 443-458
- MSC (2020): Primary 05C20
- DOI: https://doi.org/10.1090/mcom/3887
- MathSciNet review: 4654629