A convex geometric graph $G$ is said to be packable if there exist edge-disjoint copies of $G$ in the complete convex geometric graph ${K}_{n}$ covering all but $o({n}^{2})$ edges. We prove that every convex geometric graph with cyclic chromatic number at most 4 is packable. With a similar definition of packability for ordered graphs, we prove that every ordered graph with interval chromatic number at most 3 is packable. Arguments based on the average length of edges imply these results are the best possible. We also identify a class of convex geometric graphs that are packable due to having many “long” edges.

REFERENCES

1O. Aichholzer, T. Hackl, M. Korman, M. Van Kreveld, M. Löffler, A. Pilz, B. Speckmann, and E. Welzl, Packing plane spanning trees and paths in complete geometric graphs, Inform. Process. Lett. 124 (2017), 35–41.
10.1016/j.ipl.2017.04.006
Web of Science® Google Scholar
2N. Alon and J. H. Spencer, The probabilistic method, 4th ed., John Wiley & Sons, New Jersey, 2016.
Google Scholar
3M. Axenovich, J. Rollin, and T. Ueckerdt, Chromatic number of ordered graphs with forbidden ordered subgraphs, Combinatorica. 38 (2018), no. 5, 1021–1043.
10.1007/s00493-017-3593-0
Web of Science® Google Scholar
4F. Bernhart and P. C. Kainen, The book thickness of a graph, J. Combin. Theory Ser. B. 27 (1979), no. 3, 320–331.
10.1016/0095-8956(79)90021-2
Web of Science® Google Scholar
5A. Biniaz and A. García, Packing plane spanning trees into a point set, Comput. Geom. 90 (2020), 101653.
10.1016/j.comgeo.2020.101653
Web of Science® Google Scholar
6P. Bose, F. Hurtado, E. Rivera-Campo, and D. R. Wood, Partitions of complete geometric graphs into plane trees, Comput. Geom. 34 (2006), no. 2, 116–125.
10.1016/j.comgeo.2005.08.006
Web of Science® Google Scholar
7P. Brass, G. Károlyi, and P. Valtr, A Turán-type extremal theory of convex geometric graphs, Discrete and Computational Geometry: The Goodman-Pollack Festschrift, B. Aronov, S. Basu, J. Pach, and M. Sharir (eds.), Springer, 2003, pp. 275–300.
10.1007/978-3-642-55566-4_12
Google Scholar
8D. W. Cranston, J. Nie, J. Verstraëte, and A. Wesolek, On asymptotic packing of geometric graphs, Discret. Appl. Math. 322 (2022), 142–152.
10.1016/j.dam.2022.07.030
Web of Science® Google Scholar
9Z. Füredi, A. Kostochka, D. Mubayi, and J. Verstraëte, Ordered and convex geometric trees with linear extremal function, Discrete Comput. Geom. 64 (2020), no. 2, 324–338.
10.1007/s00454-019-00149-z
Web of Science® Google Scholar
10S. Glock, D. Kühn, A. Lo, and D. Osthus, The existence of designs via iterative absorption: Hypergraph $f$ -designs for arbitrary $f$ , Mem. Am. Math. Soc. 284 (2023), 1406.
Web of Science® Google Scholar
11E. Győri, D. Korándi, A. Methuku, I. Tomon, C. Tompkins, and M. Vizer, On the Turán number of some ordered even cycles, European J. Combin. 73 (2018), 81–88.
10.1016/j.ejc.2018.05.008
Web of Science® Google Scholar
12P. Keevash, The existence of designs, arXiv preprint arXiv:1401.3665, 2014.
Google Scholar
13T. P. Kirkman, On a problem in combinations, Cambridge Dublin Math. J. 2 (1847), 191–204.
Google Scholar
14J. Matoušek and B. Gärtner, Understanding and using linear programming, Springer Science & Business Media, Berlin, 2006.
Google Scholar
15J. Obenaus and J. Orthaber, Edge partitions of complete geometric graphs (part 1), arXiv preprint arXiv:2108.05159, 2021.
Google Scholar
16J. Pach and G. Tardos, Forbidden paths and cycles in ordered graphs and matrices, Israel J. Math. 155 (2006), no. 1, 359–380.
10.1007/BF02773960
Google Scholar
17N. Pippenger and J. Spencer, Asymptotic behavior of the chromatic index for hypergraphs, J. Combin. Theory Ser. A. 51 (1989), no. 1, 24–42.
10.1016/0097-3165(89)90074-5
Web of Science® Google Scholar
18V. Rödl and L. Thoma, Asymptotic packing and the random greedy algorithm, Random Structures Algorithms. 8 (1996), no. 3, 161–177.
10.1002/(SICI)1098-2418(199605)8:3<161::AID-RSA1>3.0.CO;2-W
Web of Science® Google Scholar
19V. Rödl, On a packing and covering problem, European J. Combin. 6 (1985), no. 1, 69–78.
10.1016/S0195-6698(85)80023-8
Google Scholar
20H. M. Trao, G. L. Chia, N. A. Ali, and A. Kilicman, On edge-partitioning of complete geometric graphs into plane trees, arXiv preprint arXiv:1906.05598, 2019.
Google Scholar
21R. M. Wilson, Decompositions of complete graphs into subgraphs isomorphic to a given graph, Proceedings of the 5th British Combinatorial Conference, C. Nash-Williams, and J. Sheehan (eds.), Utilitas Mathematica Pub., Winnipeg. 1975.
Google Scholar
22R. Yuster, Combinatorial and computational aspects of graph packing and graph decomposition, Comput. Sci. Rev. 1 (2007), no. 1, 12–26.
10.1016/j.cosrev.2007.07.002
Google Scholar

Volume104, Issue4

December 2023

Pages 836-850

On asymptotic packing of convex geometric and ordered graphs

Abstract

REFERENCES

References

Information

About Wiley Online Library

Help & Support

Opportunities

Connect with Wiley

On asymptotic packing of convex geometric and ordered graphs

Abstract

REFERENCES

References

Related

Information