# Mathematics of Computation

Published by the American Mathematical Society since 1960 (published as Mathematical Tables and other Aids to Computation 1943-1959), Mathematics of Computation is devoted to research articles of the highest quality in computational mathematics.

ISSN 1088-6842 (online) ISSN 0025-5718 (print)

The 2020 MCQ for Mathematics of Computation is 1.78.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

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

## 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
Similar Articles
• Retrieve articles in Mathematics of Computation with MSC (2020): 05C20
• Retrieve articles in all journals with MSC (2020): 05C20
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
• 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.