Packing of graphs with small product of sizes

Alexandr V. Kostochka; Gexin Yu

doi:10.1016/j.jctb.2008.02.004

Packing of graphs with small product of sizes

Alexandr V. Kostochka
, Gexin Yu

Mathematics

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

Abstract

We show that for every ε{lunate} > 0, there exists n₀ = n₀ (ε{lunate}) such that for every n > n₀, two n-vertex graphs G₁ and G₂ with e (G₁) e (G₂) ≤ (1 - ε{lunate}) n² pack, unless they belong to a well-defined family of exceptions. This extends a well-known result by Sauer and Spencer.

Original language	English (US)
Pages (from-to)	1411-1415
Number of pages	5
Journal	Journal of Combinatorial Theory. Series B
Volume	98
Issue number	6
DOIs	https://doi.org/10.1016/j.jctb.2008.02.004
State	Published - Nov 2008

Keywords

Graph packing

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Online availability

10.1016/j.jctb.2008.02.004

Library availability

Discover UIUC Full Text

Cite this

@article{d9525d1fa3c849d3a3177b27a54280d6,

title = "Packing of graphs with small product of sizes",

abstract = "We show that for every ε\{lunate\} > 0, there exists n0 = n0 (ε\{lunate\}) such that for every n > n0, two n-vertex graphs G1 and G2 with e (G1) e (G2) ≤ (1 - ε\{lunate\}) n2 pack, unless they belong to a well-defined family of exceptions. This extends a well-known result by Sauer and Spencer.",

keywords = "Graph packing",

author = "Kostochka, \{Alexandr V.\} and Gexin Yu",

note = "E-mail addresses: [email protected] (A.V. Kostochka), [email protected] (G. Yu). 1 Research supported in part by NSF grant DMS-0650784 and RFBR grant 05-01-00816. 2 Research supported in part by NSF grant DMS-0652306.",

year = "2008",

month = nov,

doi = "10.1016/j.jctb.2008.02.004",

language = "English (US)",

volume = "98",

pages = "1411--1415",

journal = "Journal of Combinatorial Theory. Series B",

issn = "0095-8956",

publisher = "Academic Press Inc.",

number = "6",

}

TY - JOUR

T1 - Packing of graphs with small product of sizes

AU - Kostochka, Alexandr V.

AU - Yu, Gexin

N1 - E-mail addresses: [email protected] (A.V. Kostochka), [email protected] (G. Yu). 1 Research supported in part by NSF grant DMS-0650784 and RFBR grant 05-01-00816. 2 Research supported in part by NSF grant DMS-0652306.

PY - 2008/11

Y1 - 2008/11

N2 - We show that for every ε{lunate} > 0, there exists n0 = n0 (ε{lunate}) such that for every n > n0, two n-vertex graphs G1 and G2 with e (G1) e (G2) ≤ (1 - ε{lunate}) n2 pack, unless they belong to a well-defined family of exceptions. This extends a well-known result by Sauer and Spencer.

AB - We show that for every ε{lunate} > 0, there exists n0 = n0 (ε{lunate}) such that for every n > n0, two n-vertex graphs G1 and G2 with e (G1) e (G2) ≤ (1 - ε{lunate}) n2 pack, unless they belong to a well-defined family of exceptions. This extends a well-known result by Sauer and Spencer.

KW - Graph packing

UR - https://www.scopus.com/pages/publications/52149107746

UR - https://www.scopus.com/pages/publications/52149107746#tab=citedBy

U2 - 10.1016/j.jctb.2008.02.004

DO - 10.1016/j.jctb.2008.02.004

M3 - Article

AN - SCOPUS:52149107746

SN - 0095-8956

VL - 98

SP - 1411

EP - 1415

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

IS - 6

ER -

Packing of graphs with small product of sizes

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this