Semidegree, edge density and antidirected subgraphs

EUROCOMB’23

Maya Stein Camila Zárate-Guerén

https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-113

PDF
Abstract
An oriented graph is called anti-directed if it has no directed path with $2$ edges. We prove that asymptotically, any oriented graph $D$ of minimum semidegree greater than $\frac k2$ contains every balanced antidirected tree of bounded degree and with $k$ edges, and $D$ also contains every antidirected subdivision $H$ of a sufficiently small complete graph $K_h$, with a mild restriction on the lengths of the antidirected paths in $H$ replacing the edges of $K_h$, and with $H$ having a total of $k$ edges. Further, we address a conjecture of Addario-Berry, Havet, Linhares Sales, Reed and Thomassé stating that every digraph on $n$ vertices and with more than $(k-1)n$ edges contains all antidirected trees with $k$ edges. We show that their conjecture is asymptotically true in oriented graphs for balanced antidirected trees of bounded degree and size linear in $n$.

Pages:
819–825
References

Pierre Aboulker, Nathann Cohen, Frédéric Havet, William Lochet, Phablo Moura, and Stéphan Thomassé. Subdivisions in digraphs of large out-degree or large dichromatic number. The Electronic Journal of Combinatorics, 26:3.19, 2019.
https://doi.org/10.37236/6521

Louigi Addario-Berry, Frédéric Havet, Cláudia Linhares Sales, Bruce Reed, and Stéphan Thomassé. Oriented trees in digraphs. Discrete Mathematics, 313(8):967-974, 2013.
https://doi.org/10.1016/j.disc.2013.01.011

Miklós Ajtai, János Komlós, and Endre Szemerédi. On a conjecture of Loebl. Proc. of the 7th International Conference on Graph theory, combinatorics, and algorithms, 1(2):1135-1146, 1995.

Stefan Burr. Subtrees of directed graphs and hypergraphs. Proc. of the 11th South-eastern Conference on Combinatorics, Graph Theory and Combinatorics (Florida Atlantic Univ., Boca Raton, Fla.), 28(I):227-239, 1980.

Paul Erdős and Tibor Gallai. On maximal paths and circuits of graphs. Acta Mathematica Academiae Scientiarum Hungarica, 10:337-356, 1959.
https://doi.org/10.1007/BF02024498

Ronald L. Graham. On subtrees of directed graphs with no path of length exceeding one. Canad. Math. Bull., 13(3):329-332, 1970.
https://doi.org/10.4153/CMB-1970-063-1

Bill Jackson. Long paths and cycles in oriented graphs. Journal of Graph Theory, 5(2):145-157, 1981.
https://doi.org/10.1002/jgt.3190050204

Amarja Kathapurkar and Richard Montgomery. Spanning trees in dense directed graphs. J. Combinatorial Theory Series B, 156:223-249, 2022.
https://doi.org/10.1016/j.jctb.2022.04.007

Luke Kelly, Daniela Kühn, and Deryk Osthus. Cycles of given length in oriented graphs. J. Combinatorial Theory Series B, 100(3):251-264, 2010.
https://doi.org/10.1016/j.jctb.2009.08.002

János Komlós, Gábor N. Sárközy, and Endre Szemerédi. Proof of a packing conjecture of Bollobás. Combinatorics, Probability and Computing, 4(3):241-255, 1995.
https://doi.org/10.1017/S0963548300001620

Wolfgang Mader. Homomorphieeigenschaften und mittlere kantendichte von graphen. Mathematische Annalen, 174:265-268, 1967.
https://doi.org/10.1007/BF01364272

Wolfgang Mader. Degree and local connectivity in digraphs. Combinatorica, 5:161-165, 1985.
https://doi.org/10.1007/BF02579379

Maya Stein. Tree containment and degree conditions. In Raigorodskii, A.M., Rassias, M.T. (editors). Discrete Mathematics and Applications, 165:459-486, 2020. Springer.
https://doi.org/10.1007/978-3-030-55857-4_19

Maya Stein and Camila Zárate-Guerén. Antidirected subgraphs of oriented graphs. Preprint 2022, arXiv 2212.00769.

Carster Thomassen. Even cycles in directed graphs. European Journal of Combinatorics, 6(1):85-89, 1985.
https://doi.org/10.1016/S0195-6698(85)80025-1

Metrics

0

Views

0

PDF views

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Copyright © 2023 Maya Stein, Camila Zárate-Guerén

PDF