Hostname: page-component-586b7cd67f-gb8f7 Total loading time: 0 Render date: 2024-11-22T19:34:42.629Z Has data issue: false hasContentIssue false

Strong complete minors in digraphs

Published online by Cambridge University Press:  24 September 2021

Maria Axenovich
Affiliation:
Department of Mathematics, Karlsruhe Institute of Technology, 76131 Karlsruhe, Germany
António Girão*
Affiliation:
School of Mathematics, University of Birmingham, Edgbaston, Birmingham, B15 2TT, United Kingdom
Richard Snyder
Affiliation:
Department of Mathematics, Karlsruhe Institute of Technology, 76131 Karlsruhe, Germany
Lea Weber
Affiliation:
Department of Mathematics, Karlsruhe Institute of Technology, 76131 Karlsruhe, Germany
*
*Corresponding author. Email:tzgirao@gmail.com

Abstract

Kostochka and Thomason independently showed that any graph with average degree $\Omega(r\sqrt{\log r})$ contains a $K_r$ minor. In particular, any graph with chromatic number $\Omega(r\sqrt{\log r})$ contains a $K_r$ minor, a partial result towards Hadwiger’s 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 $\overrightarrow{K}_{\!\!r}$ minor is a digraph whose vertex set is partitioned into r 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 $\overrightarrow{K}_{\!\!r}$ minors as subdigraphs. In particular, we show that any tournament with dichromatic number at least 2r contains a strong $\overrightarrow{K}_{\!\!r}$ minor, and any tournament with minimum out-degree $\Omega(r\sqrt{\log r})$ also contains a strong $\overrightarrow{K}_{\!\!r}$ 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 $f\;:\;\mathbb{N} \rightarrow \mathbb{N}$ such that any digraph with minimum out-degree at least f(r) contains a strong $\overrightarrow{K}_{\!\!r}$ minor, but such a function exists when considering dichromatic number.

Type
Paper
Copyright
© The Author(s), 2021. Published by Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Aboulker, P., Cohen, N., Havet, F., Lochet, W., Moura, P. F., and Thomassé, S., Subdivisions in digraphs of large out-degree or large dichromatic number, Electronic Journal of Combinatorics 26 (2019), no. 3.CrossRefGoogle Scholar
Berger, E., Choromanski, K., Chudnovsky, M., Fox, J., Loebl, M., Scott, A., Seymour, P., and Thomassé, S., Tournaments and colouring, Journal of Combinatorial Theory, Series B 103 (2013), no. 1, 120.CrossRefGoogle Scholar
Bollobás, B., Catlin, P. A, and Erdös, P., Hadwiger’s conjecture is true for almost every graph., Eur. J. Comb. 1 (1980), no. 3, 195–199.Google Scholar
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–92.Google Scholar
Girão, A., Popielarz, K., and Snyder, R., Subdivisions of digraphs in tournaments , Journal of Combinatorial Theory, Series B 146 (2021), 266285.CrossRefGoogle Scholar
Gishboliner, L., Steiner, R., and Szabó, T., Dichromatic number and forced subdivisions, arXiv preprint arXiv:2008.09888 (2020).Google Scholar
Gishboliner, L., Steiner, R., and Szabó, T., Oriented cycles in digraphs of large outdegree, arXiv preprint arXiv:2008.13224 (2020).Google Scholar
Hadwiger, H., Uber eine Klassifikation der Streckenkomplexe, Vierteljschr. Naturforsch. Ges. ZÜrich 88 (1943), no. 2, 133–142.Google Scholar
Harutyunyan, A., Le, T.-N., Newman, A., and Thomassé, S., Coloring Dense Digraphs , Combinatorica 39 (2019), 10211053.CrossRefGoogle Scholar
Harutyunyan, A., Le, T.-N., Thomassé, S., and Wu, H., Coloring tournaments: From local to global , Journal of Combinatorial Theory, Series B 138 (2019), 166171.CrossRefGoogle Scholar
Jagger, C., An extremal function for digraph subcontraction, Journal of Graph Theory 21 (1996), no. 3, 343–350.Google Scholar
Jagger, C., Extremal digraph results for topological complete subgraphs, European Journal of Combinatorics 19 (1998), no. 6, 687–694.Google Scholar
Johnson, T., Robertson, N., Seymour, P. D., and Thomas, R., Directed Tree-Width, Journal of Combinatorial Theory, Series B 82 (2001), no. 1, 138154.Google Scholar
Kim, I. and Seymour, P., Tournament minors , Journal of Combinatorial Theory, Series B 112 (2015), 138153.CrossRefGoogle Scholar
Kostochka, A. V., Lower bound of the Hadwiger number of graphs by their average degree, Combinatorica 4 (1984), no. 4, 307316.Google Scholar
Neumann-Lara, V., The Dichromatic Number of a Digraph , Journal of Combinatorial Theory, Series B 33 (1982), 265270.CrossRefGoogle Scholar
Norin, S. and Song, Z.-X., Breaking the degeneracy barrier for coloring graphs with no Kt minor, arXiv preprint arXiv:1910.09378 (2019).Google Scholar
Pokrovskiy, A., Highly linked tournaments , Journal of Combinatorial Theory, Series B 115 (2015), 339347.CrossRefGoogle Scholar
Postle, L., Halfway to Hadwiger’s Conjecture, arXiv preprint arXiv:1911.01491 (2019).Google Scholar
Postle, L., Further progress towards Hadwiger’s conjecture, arXiv preprint arXiv:2006.11798 (2020).Google Scholar
Robertson, N., Seymour, P., and Thomas, R., Hadwiger’s conjecture forK 6-free graphs, Combinatorica 13 (1993), no. 3, 279361.Google Scholar
Thomason, A., An extremal function for contractions of graphs, Mathematical Proceedings of the Cambridge Philosophical Society, 1984, pp. 261265.Google Scholar
Thomassen, C., Even cycles in directed graphs, European Journal of Combinatorics 6 (1985), no. 1, 8589.Google Scholar
Wagner, K., Uber eine Eigenschaft der ebenen Komplexe, Mathematische Annalen 114 (1937), no. 1, 570590.Google Scholar