Hostname: page-component-cd9895bd7-jn8rn Total loading time: 0 Render date: 2024-12-26T17:58:33.243Z Has data issue: false hasContentIssue false
  • English
  • Français

Packing Graphs of Bounded Codegree

Part of: Graph theory

Published online by Cambridge University Press:  22 March 2018

WOUTER CAMES VAN BATENBURG  and
ROSS J. KANG
WOUTER CAMES VAN BATENBURG
Affiliation:
Department of Mathematics, Radboud University Nijmegen, PO Box 9010, 6500 GL Nijmegen, Netherlands (e-mail: [email protected], [email protected])
ROSS J. KANG
Affiliation:
Department of Mathematics, Radboud University Nijmegen, PO Box 9010, 6500 GL Nijmegen, Netherlands (e-mail: [email protected], [email protected])
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Two graphs G1 and G2 on n vertices are said to pack if there exist injective mappings of their vertex sets into [n] such that the images of their edge sets are disjoint. A longstanding conjecture due to Bollobás and Eldridge and, independently, Catlin, asserts that if (Δ(G1) + 1)(Δ(G2) + 1) ⩽ n + 1, then G1 and G2 pack. We consider the validity of this assertion under the additional assumption that G1 or G2 has bounded codegree. In particular, we prove for all t ⩾ 2 that if G1 contains no copy of the complete bipartite graph K2,t and Δ(G1) > 17t · Δ(G2), then (Δ(G1) + 1)(Δ(G2) + 1) ⩽ n + 1 implies that G1 and G2 pack. We also provide a mild improvement if moreover G2 contains no copy of the complete tripartite graph K1,1,s, s ⩾ 1.

MSC classification

Primary: 05C70: Factorization, matching, partitioning, covering and packing
Secondary: 05C35: Extremal problems
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 27 , Issue 5 , September 2018 , pp. 725 - 740
Creative Commons
Creative Common License - CCCreative Common License - BY
This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted re-use, distribution, and reproduction in any medium, provided the original work is properly cited.
Copyright
Copyright © Cambridge University Press 2018

Footnotes

†

Supported by NWO grant 613.001.217.

‡

Supported by a NWO Vidi grant (639.032.614).

References

[1] Aigner, M. and Brandt, S. (1993) Embedding arbitrary graphs of maximum degree two. J. London Math. Soc. (2) 48 39–51.Google Scholar
[2] Bollobás, B. and Eldridge, S. E. (1978) Packings of graphs and applications to computational complexity. J. Combin. Theory Ser. B 25 105–124.Google Scholar
[3] Bollobás, B., Janson, S. and Scott, A. (2017) Packing random graphs and hypergraphs. Random Struct. Alg. 51 3–13.Google Scholar
[4] Bollobás, B., Kostochka, A. and Nakprasit, K. (2005) On two conjectures on packing of graphs. Combin. Probab. Comput. 14 723–736.Google Scholar
[5] Bollobás, B., Kostochka, A. and Nakprasit, K. (2008) Packing d-degenerate graphs. J. Combin. Theory Ser. B 98 85–94.Google Scholar
[6] Catlin, P. A. (1974) Subgraphs of graphs I. Discrete Math. 10 225–233.Google Scholar
[7] Catlin, P. A. (1976) Embedding subgraphs and coloring graphs under extremal degree conditions. PhD thesis, The Ohio State University. ProQuest LLC, Ann Arbor, MI.Google Scholar
[8] Corrádi, K. (1969) Problem at Schweitzer competition. Mat. Lapok 20 159–162.Google Scholar
[9] Csaba, B. (2007) On the Bollobás–Eldridge conjecture for bipartite graphs. Combin. Probab. Comput. 16 661–691.Google Scholar
[10] Csaba, B., Shokoufandeh, A. and Szemerédi, E. (2003) Proof of a conjecture of Bollobás and Eldridge for graphs of maximum degree three. Combinatorica 23 35–72.Google Scholar
[11] Eaton, N. (2000) A near packing of two graphs. J. Combin. Theory Ser. B 80 98–103.Google Scholar
[12] Hajnal, A. and Szemerédi, E. (1970) Proof of a conjecture of P. Erdős. In Combinatorial Theory and its Applications II: (Proc. Colloq., Balatonfüred, 1969), North-Holland, pp. 601–623.Google Scholar
[13] Johansson, A. (1996) Asymptotic choice number for triangle-free graphs. Technical report 91-5, DIMACS.Google Scholar
[14] Kaul, H. and Kostochka, A. (2007) Extremal graphs for a graph packing theorem of Sauer and Spencer. Combin. Probab. Comput. 16 409–416.Google Scholar
[15] Kaul, H., Kostochka, A. and Yu, G. (2008) On a graph packing conjecture by Bollobás, Eldridge and Catlin. Combinatorica 28 469–485.Google Scholar
[16] Molloy, M. and Reed, B. (2002) Graph Colouring and the Probabilistic Method, Vol. 23 of Algorithms and Combinatorics, Springer.Google Scholar
[17] Sauer, N. and Spencer, J. (1978) Edge disjoint placement of graphs. J. Combin. Theory Ser. B 25 295–302.Google Scholar