{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,6,13]],"date-time":"2024-06-13T01:39:29Z","timestamp":1718242769743},"reference-count":24,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2021,9,24]],"date-time":"2021-09-24T00:00:00Z","timestamp":1632441600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2022,5]]},"abstract":"Abstract<\/jats:title>Kostochka and Thomason independently showed that any graph with average degree \n$\\Omega(r\\sqrt{\\log r})$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> contains a \n$K_r$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> minor. In particular, any graph with chromatic number \n$\\Omega(r\\sqrt{\\log r})$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> contains a \n$K_r$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> minor, a partial result towards Hadwiger\u2019s famous conjecture. In this paper, we investigate analogues of these results in the directed setting. There are several ways to define a minor in a digraph. One natural way is as follows. A strong<\/jats:italic>\n$\\overrightarrow{K}_{\\!\\!r}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>minor<\/jats:italic> is a digraph whose vertex set is partitioned into r<\/jats:italic> parts such that each part induces a strongly connected subdigraph, and there is at least one edge in each direction between any two distinct parts. We investigate bounds on the dichromatic number and minimum out-degree of a digraph that force the existence of strong \n$\\overrightarrow{K}_{\\!\\!r}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> minors as subdigraphs. In particular, we show that any tournament with dichromatic number at least 2r<\/jats:italic> contains a strong \n$\\overrightarrow{K}_{\\!\\!r}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> minor, and any tournament with minimum out-degree \n$\\Omega(r\\sqrt{\\log r})$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> also contains a strong \n$\\overrightarrow{K}_{\\!\\!r}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> minor. The latter result is tight up to the implied constant and may be viewed as a strong-minor analogue to the classical result of Kostochka and Thomason. Lastly, we show that there is no function \n$f\\;:\\;\\mathbb{N} \\rightarrow \\mathbb{N}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> such that any digraph with minimum out-degree at least f<\/jats:italic>(r<\/jats:italic>) contains a strong \n$\\overrightarrow{K}_{\\!\\!r}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> minor, but such a function exists when considering dichromatic number.<\/jats:p>","DOI":"10.1017\/s0963548321000390","type":"journal-article","created":{"date-parts":[[2021,9,25]],"date-time":"2021-09-25T00:49:24Z","timestamp":1632530964000},"page":"489-506","update-policy":"http:\/\/dx.doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":2,"title":["Strong complete minors in digraphs"],"prefix":"10.1017","volume":"31","author":[{"given":"Maria","family":"Axenovich","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ant\u00f3nio","family":"Gir\u00e3o","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Richard","family":"Snyder","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lea","family":"Weber","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2021,9,24]]},"reference":[{"key":"S0963548321000390_ref2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2012.08.003"},{"key":"S0963548321000390_ref14","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2014.12.005"},{"key":"S0963548321000390_ref3","doi-asserted-by":"crossref","unstructured":"[3] Bollob\u00e1s, B. , Catlin, P. A , and Erd\u00f6s, P. , Hadwiger\u2019s conjecture is true for almost every graph., Eur. J. Comb. 1 (1980), no. 3, 195\u2013199.","DOI":"10.1016\/S0195-6698(80)80001-1"},{"key":"S0963548321000390_ref15","first-page":"307","volume":"4","author":"Kostochka","year":"1984","journal-title":"Lower bound of the Hadwiger number of graphs by their average degree"},{"key":"S0963548321000390_ref16","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(82)90046-6"},{"key":"S0963548321000390_ref23","first-page":"85","volume":"1","author":"Thomassen","year":"1985","journal-title":"Even cycles in directed graphs"},{"key":"S0963548321000390_ref12","doi-asserted-by":"crossref","unstructured":"[12] Jagger, C. , Extremal digraph results for topological complete subgraphs, European Journal of Combinatorics 19 (1998), no. 6, 687\u2013694.","DOI":"10.1006\/eujc.1998.0231"},{"key":"S0963548321000390_ref6","unstructured":"[6] Gishboliner, L. , Steiner, R. , and Szab\u00f3, T. , Dichromatic number and forced subdivisions, arXiv preprint arXiv:2008.09888 (2020)."},{"key":"S0963548321000390_ref13","first-page":"138","volume":"1","author":"Johnson","year":"2001","journal-title":"Directed Tree-Width"},{"key":"S0963548321000390_ref18","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2015.05.005"},{"key":"S0963548321000390_ref5","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2020.09.006"},{"key":"S0963548321000390_ref10","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2019.01.005"},{"key":"S0963548321000390_ref11","doi-asserted-by":"crossref","unstructured":"[11] Jagger, C. , An extremal function for digraph subcontraction, Journal of Graph Theory 21 (1996), no. 3, 343\u2013350.","DOI":"10.1002\/(SICI)1097-0118(199603)21:3<343::AID-JGT10>3.0.CO;2-I"},{"key":"S0963548321000390_ref20","unstructured":"[20] Postle, L. , Further progress towards Hadwiger\u2019s conjecture, arXiv preprint arXiv:2006.11798 (2020)."},{"key":"S0963548321000390_ref22","first-page":"261","author":"Thomason","year":"1984","journal-title":"An extremal function for contractions of graphs"},{"key":"S0963548321000390_ref21","first-page":"279","volume":"3","author":"Robertson","year":"1993","journal-title":"Hadwiger\u2019s conjecture forK 6-free graphs"},{"key":"S0963548321000390_ref17","unstructured":"[17] Norin, S. and Song, Z.-X. , Breaking the degeneracy barrier for coloring graphs with no Kt minor, arXiv preprint arXiv:1910.09378 (2019)."},{"key":"S0963548321000390_ref1","doi-asserted-by":"publisher","DOI":"10.37236\/6521"},{"key":"S0963548321000390_ref19","unstructured":"[19] Postle, L. , Halfway to Hadwiger\u2019s Conjecture, arXiv preprint arXiv:1911.01491 (2019)."},{"key":"S0963548321000390_ref9","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-019-3815-8"},{"key":"S0963548321000390_ref8","unstructured":"[8] Hadwiger, H. , Uber eine Klassifikation der Streckenkomplexe, Vierteljschr. Naturforsch. Ges. Z\u00dcrich 88 (1943), no. 2, 133\u2013142."},{"key":"S0963548321000390_ref4","doi-asserted-by":"crossref","unstructured":"[4] Dirac, G. A , A property of 4-chromatic graphs and some remarks on critical graphs, Journal of the London Mathematical Society 1 (1952), no. 1, 85\u201392.","DOI":"10.1112\/jlms\/s1-27.1.85"},{"key":"S0963548321000390_ref7","unstructured":"[7] Gishboliner, L. , Steiner, R. , and Szab\u00f3, T. , Oriented cycles in digraphs of large outdegree, arXiv preprint arXiv:2008.13224 (2020)."},{"key":"S0963548321000390_ref24","first-page":"570","volume":"1","author":"Wagner","year":"1937","journal-title":"Uber eine Eigenschaft der ebenen Komplexe"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548321000390","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,4,20]],"date-time":"2022-04-20T11:36:26Z","timestamp":1650454586000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548321000390\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,9,24]]},"references-count":24,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,5]]}},"alternative-id":["S0963548321000390"],"URL":"https:\/\/doi.org\/10.1017\/s0963548321000390","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,9,24]]},"assertion":[{"value":"\u00a9 The Author(s), 2021. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}]}}