On packing bipartite graphs

Péter Hajnal; Márió Szegedy

doi:10.1007/BF01285818

On packing bipartite graphs

Péter Hajnal, Márió Szegedy

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

9 Scopus citations

Abstract

G and H, two simple graphs, can be packed if G is isomorphic to a subgraph of {Mathematical expression}, the complement of H. A theorem of Catlin, Spencer and Sauer gives a sufficient condition for the existence of packing in terms of the product of the maximal degrees of G and H. We improve this theorem for bipartite graphs. Our condition involves products of a maximum degree with an average degree. Our relaxed condition still guarantees a packing of the two bipartite graphs.

Original language	English (US)
Pages (from-to)	295-301
Number of pages	7
Journal	Combinatorica
Volume	12
Issue number	3
DOIs	https://doi.org/10.1007/BF01285818
State	Published - Sep 1992
Externally published	Yes

All Science Journal Classification (ASJC) codes

Discrete Mathematics and Combinatorics
Computational Mathematics

Keywords

AMS subject classification code (1991): 05C70

Access to Document

10.1007/BF01285818

Cite this

@article{2e734cbb81a04b3d9f5ea8d8aac81414,

title = "On packing bipartite graphs",

abstract = "G and H, two simple graphs, can be packed if G is isomorphic to a subgraph of {Mathematical expression}, the complement of H. A theorem of Catlin, Spencer and Sauer gives a sufficient condition for the existence of packing in terms of the product of the maximal degrees of G and H. We improve this theorem for bipartite graphs. Our condition involves products of a maximum degree with an average degree. Our relaxed condition still guarantees a packing of the two bipartite graphs.",

keywords = "AMS subject classification code (1991): 05C70",

author = "P{\'e}ter Hajnal and M{\'a}ri{\'o} Szegedy",

year = "1992",

month = sep,

doi = "10.1007/BF01285818",

language = "English (US)",

volume = "12",

pages = "295--301",

journal = "Combinatorica",

issn = "0209-9683",

publisher = "Janos Bolyai Mathematical Society",

number = "3",

}

TY - JOUR

T1 - On packing bipartite graphs

AU - Hajnal, Péter

AU - Szegedy, Márió

PY - 1992/9

Y1 - 1992/9

N2 - G and H, two simple graphs, can be packed if G is isomorphic to a subgraph of {Mathematical expression}, the complement of H. A theorem of Catlin, Spencer and Sauer gives a sufficient condition for the existence of packing in terms of the product of the maximal degrees of G and H. We improve this theorem for bipartite graphs. Our condition involves products of a maximum degree with an average degree. Our relaxed condition still guarantees a packing of the two bipartite graphs.

AB - G and H, two simple graphs, can be packed if G is isomorphic to a subgraph of {Mathematical expression}, the complement of H. A theorem of Catlin, Spencer and Sauer gives a sufficient condition for the existence of packing in terms of the product of the maximal degrees of G and H. We improve this theorem for bipartite graphs. Our condition involves products of a maximum degree with an average degree. Our relaxed condition still guarantees a packing of the two bipartite graphs.

KW - AMS subject classification code (1991): 05C70

UR - http://www.scopus.com/inward/record.url?scp=33244485195&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33244485195&partnerID=8YFLogxK

U2 - 10.1007/BF01285818

DO - 10.1007/BF01285818

M3 - Article

AN - SCOPUS:33244485195

SN - 0209-9683

VL - 12

SP - 295

EP - 301

JO - Combinatorica

JF - Combinatorica

IS - 3

ER -

On packing bipartite graphs

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this