Packing Degenerate Graphs Greedily

Autoři: Diana Piguet
Rok vydání: 2017
Typ publikace: Článek v odborném periodiku
Periodikum: Electronic Notes in Discrete Mathematics
Projekty: Extremální teorie grafů a aplikace
Bibliografická citace: 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

Abstrakt

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.