Packing Degenerate Graphs Greedily

Authors: P. Allen, J. Böttcher, J. Hladký, Diana Piguet
Publication year: 2017
Publication type: Článek v odborném periodiku
Periodical: Electronic Notes in Discrete Mathematics
Projects: Extremal graph theory and applications
Bibliographic citation: ALLEN, P., BÖTTCHER, J., HLADKÝ, J., PIGUET, Diana. Packing Degenerate Graphs Greedily. Electronic Notes in Discrete Mathematics. 2017, 61(August), 45-51. ISSN 1571-0653
Dostupné z: doi:10.1016/j.endm.2017.06.019
DOI: 10.1016/j.endm.2017.06.019
ID: 477019

Abstract

We prove that if G is a family of graphs with at most n vertices each, with constant degeneracy, with maximum degree at most O(n/log n), and with total number of edges at most (1-o(1)) n^2/2, then G packs into the complete graph on n vertices.