{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,6,28]],"date-time":"2024-06-28T18:14:54Z","timestamp":1719598494511},"reference-count":18,"publisher":"American Mathematical Society (AMS)","issue":"345","license":[{"start":{"date-parts":[[2024,7,11]],"date-time":"2024-07-11T00:00:00Z","timestamp":1720656000000},"content-version":"am","delay-in-days":366,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"funder":[{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-18-CE40-0032","ANR-18-CE40-0032","MUNI Award in Science and Humanities"],"award-info":[{"award-number":["ANR-18-CE40-0032","ANR-18-CE40-0032","MUNI Award in Science and Humanities"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"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 \n\n \n k<\/mml:mi>\n k<\/mml:annotation>\n <\/mml:semantics>\n<\/mml:math>\n<\/inline-formula>-chromatic if \n\n \n k<\/mml:mi>\n k<\/mml:annotation>\n <\/mml:semantics>\n<\/mml:math>\n<\/inline-formula> 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 \n\n \n k<\/mml:mi>\n k<\/mml:annotation>\n <\/mml:semantics>\n<\/mml:math>\n<\/inline-formula>-chromatic digraph is the complete digraph on \n\n \n k<\/mml:mi>\n k<\/mml:annotation>\n <\/mml:semantics>\n<\/mml:math>\n<\/inline-formula> vertices, but determining the order of the smallest \n\n \n k<\/mml:mi>\n k<\/mml:annotation>\n <\/mml:semantics>\n<\/mml:math>\n<\/inline-formula>-chromatic oriented graphs is a challenging problem. It is known that the smallest \n\n \n 2<\/mml:mn>\n 2<\/mml:annotation>\n <\/mml:semantics>\n<\/mml:math>\n<\/inline-formula>-, \n\n \n 3<\/mml:mn>\n 3<\/mml:annotation>\n <\/mml:semantics>\n<\/mml:math>\n<\/inline-formula>- and \n\n \n 4<\/mml:mn>\n 4<\/mml:annotation>\n <\/mml:semantics>\n<\/mml:math>\n<\/inline-formula>-chromatic oriented graphs have \n\n \n 3<\/mml:mn>\n 3<\/mml:annotation>\n <\/mml:semantics>\n<\/mml:math>\n<\/inline-formula>, \n\n \n 7<\/mml:mn>\n 7<\/mml:annotation>\n <\/mml:semantics>\n<\/mml:math>\n<\/inline-formula> and \n\n \n 11<\/mml:mn>\n 11<\/mml:annotation>\n <\/mml:semantics>\n<\/mml:math>\n<\/inline-formula> vertices, respectively. In 1994, Neumann-Lara conjectured that a smallest \n\n \n 5<\/mml:mn>\n 5<\/mml:annotation>\n <\/mml:semantics>\n<\/mml:math>\n<\/inline-formula>-chromatic oriented graph has \n\n \n 17<\/mml:mn>\n 17<\/mml:annotation>\n <\/mml:semantics>\n<\/mml:math>\n<\/inline-formula> vertices. We solve this conjecture and show that the correct order is \n\n \n 19<\/mml:mn>\n 19<\/mml:annotation>\n <\/mml:semantics>\n<\/mml:math>\n<\/inline-formula>.<\/p>","DOI":"10.1090\/mcom\/3887","type":"journal-article","created":{"date-parts":[[2023,7,11]],"date-time":"2023-07-11T19:56:52Z","timestamp":1689105412000},"page":"443-458","source":"Crossref","is-referenced-by-count":1,"title":["The smallest 5-chromatic tournament"],"prefix":"10.1090","volume":"93","author":[{"given":"Thomas","family":"Bellitto","sequence":"first","affiliation":[]},{"given":"Nicolas","family":"Bousquet","sequence":"additional","affiliation":[]},{"given":"Adam","family":"Kabela","sequence":"additional","affiliation":[]},{"given":"Th\u00e9o","family":"Pierron","sequence":"additional","affiliation":[]}],"member":"14","published-online":{"date-parts":[[2023,7,11]]},"reference":[{"key":"1","unstructured":"[ABHR22] P. Aboulker, T. Bellitto, F. Havet, and C. Rambaud, On the minimum number of arcs in \ud835\udc58-dicritical oriented graphs, 2022, arXiv:2207.01051."},{"issue":"1","key":"2","doi-asserted-by":"publisher","first-page":"Paper No. 1.63, 22","DOI":"10.37236\/8942","article-title":"Haj\u00f3s and Ore constructions for digraphs","volume":"27","author":"Bang-Jensen, J\u00f8rgen","year":"2020","journal-title":"Electron. J. Combin."},{"key":"3","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1016\/S0021-9800(70)80057-6","article-title":"The smallest triangle-free 4-chromatic 4-regular graph","volume":"9","author":"Chv\u00e1tal, V.","year":"1970","journal-title":"J. Combinatorial Theory","ISSN":"http:\/\/id.crossref.org\/issn\/0021-9800","issn-type":"print"},{"issue":"2-3","key":"4","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1016\/0166-218X(94)90019-1","article-title":"The monadic second order logic of graphs. VI. On several representations of graphs by relational structures","volume":"54","author":"Courcelle, Bruno","year":"1994","journal-title":"Discrete Appl. Math.","ISSN":"http:\/\/id.crossref.org\/issn\/0166-218X","issn-type":"print"},{"key":"5","first-page":"125","article-title":"On the representation of directed graphs as unions of orderings","volume":"9","author":"Erd\u0151s, P.","year":"1964","journal-title":"Magyar Tud. Akad. Mat. Kutat\\'{o} Int. K\\\"{o}zl.","ISSN":"http:\/\/id.crossref.org\/issn\/0541-9514","issn-type":"print"},{"key":"6","first-page":"3","article-title":"Problems and results in number theory and graph theory","author":"Erd\u0151s, Paul","year":"1980"},{"issue":"1","key":"7","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1002\/jgt.22467","article-title":"On minimal triangle-free 6-chromatic graphs","volume":"93","author":"Goedgebeur, Jan","year":"2020","journal-title":"J. Graph Theory","ISSN":"http:\/\/id.crossref.org\/issn\/0364-9024","issn-type":"print"},{"issue":"5","key":"8","doi-asserted-by":"publisher","first-page":"619","DOI":"10.1007\/s00493-014-2862-4","article-title":"The edge density of critical digraphs","volume":"35","author":"Hoshino, Richard","year":"2015","journal-title":"Combinatorica","ISSN":"http:\/\/id.crossref.org\/issn\/0209-9683","issn-type":"print"},{"issue":"1","key":"9","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1002\/jgt.3190190111","article-title":"Small graphs with chromatic number 5: a computer search","volume":"19","author":"Jensen, Tommy","year":"1995","journal-title":"J. Graph Theory","ISSN":"http:\/\/id.crossref.org\/issn\/0364-9024","issn-type":"print"},{"issue":"3","key":"10","doi-asserted-by":"publisher","first-page":"703","DOI":"10.1007\/s00373-020-02147-y","article-title":"The minimum number of edges in 4-critical digraphs of given order","volume":"36","author":"Kostochka, Alexandr V.","year":"2020","journal-title":"Graphs Combin.","ISSN":"http:\/\/id.crossref.org\/issn\/0911-0119","issn-type":"print"},{"key":"11","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1016\/j.jsc.2013.09.003","article-title":"Practical graph isomorphism, II","volume":"60","author":"McKay, Brendan D.","year":"2014","journal-title":"J. Symbolic Comput.","ISSN":"http:\/\/id.crossref.org\/issn\/0747-7171","issn-type":"print"},{"issue":"3","key":"12","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1016\/0095-8956(82)90046-6","article-title":"The dichromatic number of a digraph","volume":"33","author":"Neumann Lara, V.","year":"1982","journal-title":"J. Combin. Theory Ser. B","ISSN":"http:\/\/id.crossref.org\/issn\/0095-8956","issn-type":"print"},{"issue":"1-3","key":"13","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1016\/0012-365X(93)E0113-I","article-title":"The 3- and 4-dichromatic tournaments of minimum order","volume":"135","author":"Neumann Lara, V.","year":"1994","journal-title":"Discrete Math.","ISSN":"http:\/\/id.crossref.org\/issn\/0012-365X","issn-type":"print"},{"issue":"2","key":"14","doi-asserted-by":"publisher","first-page":"197","DOI":"10.7151\/dmgt.1119","article-title":"Dichromatic number, circulant tournaments and Zykov sums of digraphs","volume":"20","author":"Neumann-Lara, V\u00edctor","year":"2000","journal-title":"Discuss. Math. Graph Theory","ISSN":"http:\/\/id.crossref.org\/issn\/1234-3099","issn-type":"print"},{"key":"15","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1016\/S0021-9800(70)80061-8","article-title":"Disproof of a conjecture of Erd\u0151s and Moser on tournaments","volume":"9","author":"Reid, K. B.","year":"1970","journal-title":"J. Combinatorial Theory","ISSN":"http:\/\/id.crossref.org\/issn\/0021-9800","issn-type":"print"},{"issue":"2","key":"16","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/s003730050025","article-title":"On tournaments free of large transitive subtournaments","volume":"14","author":"Sanchez-Flores, Adolfo","year":"1998","journal-title":"Graphs Combin.","ISSN":"http:\/\/id.crossref.org\/issn\/0911-0119","issn-type":"print"},{"key":"17","unstructured":"[SI] Neil J. A. Sloane and The OEIS Foundation Inc., The on-line encyclopedia of integer sequences, \\url{https:\/\/oeis.org\/A000568}."},{"key":"18","doi-asserted-by":"publisher","first-page":"761","DOI":"10.2307\/2310461","article-title":"The voting problem","volume":"66","author":"Stearns, Richard","year":"1959","journal-title":"Amer. Math. Monthly","ISSN":"http:\/\/id.crossref.org\/issn\/0002-9890","issn-type":"print"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.ams.org\/mcom\/2024-93-345\/S0025-5718-2023-03887-X\/S0025-5718-2023-03887-X.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,13]],"date-time":"2023-10-13T18:42:48Z","timestamp":1697222568000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2024-93-345\/S0025-5718-2023-03887-X\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7,11]]},"references-count":18,"journal-issue":{"issue":"345","published-print":{"date-parts":[[2024,1]]}},"alternative-id":["S0025-5718-2023-03887-X"],"URL":"https:\/\/doi.org\/10.1090\/mcom\/3887","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["0025-5718","1088-6842"],"issn-type":[{"value":"0025-5718","type":"print"},{"value":"1088-6842","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,7,11]]}}}