Packing degenerate graphs

0507738 - MÚ 2020 RIV US eng J - Článek v odborném periodiku
Allen, P. - Böttcher, J. - Hladký, Jan - Piguet, Diana
Packing degenerate graphs.
Advances in Mathematics. Roč. 354, 1 October (2019), č. článku 106739. ISSN 0001-8708. E-ISSN 1090-2082
Grant CEP: GA ČR GJ16-07822Y
Institucionální podpora: RVO:67985840 ; RVO:67985807
Klíčová slova: extremal graph theory * graph packing * Tree packing conjecture
Obor OECD: Pure mathematics; Pure mathematics (UIVT-O)
Impakt faktor: 1.494, rok: 2019
Způsob publikování: Open access
http://dx.doi.org/10.1016/j.aim.2019.106739

Given D and γ>0, whenever c>0 is sufficiently small and n sufficiently large, if G is a family of D-degenerate graphs of individual orders at most n, maximum degrees at most cnlogn, and total number of edges at most (1−γ)(n2), then G packs into the complete graph Kn. Our proof proceeds by analysing a natural random greedy packing algorithm.
Trvalý link: http://hdl.handle.net/11104/0298714