On perfect packings in dense graphs

Andrew Treglown; Jozsef Balogh; Alexandr Kostochka

On perfect packings in dense graphs

Andrew Treglown, Jozsef Balogh, Alexandr Kostochka

Mathematics

Research output: Contribution to journal › Article › peer-review

6 Citations (Scopus)

91 Downloads (Pure)

Abstract

We say that a graph G has a perfect H-packing if there exists a set of vertex-disjoint copies of H which cover all the vertices in G. We consider various problems concerning perfect Hpackings: Given n, r, D ∈ N, we characterise the edge density threshold that ensures a perfect Kr-packing in any graph G on n vertices and with minimum degree δ(G) ≥ D. We also give two conjectures concerning degree sequence conditions which force a graph to contain a perfect H-packing. Other related embedding problems are also considered. Indeed, we give a structural
result concerning Kr-free graphs that satisfy a certain degree sequence condition.

Original language	English
Article number	P57
Journal	The Electronic Journal of Combinatorics
Volume	20
Issue number	1
Publication status	Published - 12 Mar 2013

Keywords

packings
equitable colourings

Access to Document

Balogh_et_al_On_perfect_packings_The_Electronic_Journal_of_Combinatorics_2013Final published version, 163 KBLicence: None: All rights reserved

http://www.combinatorics.org/ojs/index.php/eljc/article/view/v20i1p57Licence: None: All rights reserved

Cite this

@article{23602a1d16c34e2f8f7c72760b0f51af,

title = "On perfect packings in dense graphs",

abstract = "We say that a graph G has a perfect H-packing if there exists a set of vertex-disjoint copies of H which cover all the vertices in G. We consider various problems concerning perfect Hpackings: Given n, r, D ∈ N, we characterise the edge density threshold that ensures a perfect Kr-packing in any graph G on n vertices and with minimum degree δ(G) ≥ D. We also give two conjectures concerning degree sequence conditions which force a graph to contain a perfect H-packing. Other related embedding problems are also considered. Indeed, we give a structuralresult concerning Kr-free graphs that satisfy a certain degree sequence condition.",

keywords = "packings , equitable colourings",

author = "Andrew Treglown and Jozsef Balogh and Alexandr Kostochka",

year = "2013",

month = mar,

day = "12",

language = "English",

volume = "20",

journal = "The Electronic Journal of Combinatorics",

issn = "1077-8926",

publisher = "Electronic Journal of Combinatorics",

number = "1",

}

TY - JOUR

T1 - On perfect packings in dense graphs

AU - Treglown, Andrew

AU - Balogh, Jozsef

AU - Kostochka, Alexandr

PY - 2013/3/12

Y1 - 2013/3/12

N2 - We say that a graph G has a perfect H-packing if there exists a set of vertex-disjoint copies of H which cover all the vertices in G. We consider various problems concerning perfect Hpackings: Given n, r, D ∈ N, we characterise the edge density threshold that ensures a perfect Kr-packing in any graph G on n vertices and with minimum degree δ(G) ≥ D. We also give two conjectures concerning degree sequence conditions which force a graph to contain a perfect H-packing. Other related embedding problems are also considered. Indeed, we give a structuralresult concerning Kr-free graphs that satisfy a certain degree sequence condition.

AB - We say that a graph G has a perfect H-packing if there exists a set of vertex-disjoint copies of H which cover all the vertices in G. We consider various problems concerning perfect Hpackings: Given n, r, D ∈ N, we characterise the edge density threshold that ensures a perfect Kr-packing in any graph G on n vertices and with minimum degree δ(G) ≥ D. We also give two conjectures concerning degree sequence conditions which force a graph to contain a perfect H-packing. Other related embedding problems are also considered. Indeed, we give a structuralresult concerning Kr-free graphs that satisfy a certain degree sequence condition.

KW - packings

KW - equitable colourings

M3 - Article

SN - 1077-8926

VL - 20

JO - The Electronic Journal of Combinatorics

JF - The Electronic Journal of Combinatorics

IS - 1

M1 - P57

ER -

On perfect packings in dense graphs

Abstract

Keywords

Access to Document

Fingerprint

Cite this