On packing bipartite graphs

Péter Hajnal, Márió Szegedy

Research output: Contribution to journalArticlepeer-review

8 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 languageEnglish (US)
Pages (from-to)295-301
Number of pages7
JournalCombinatorica
Volume12
Issue number3
DOIs
StatePublished - Sep 1992
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics

Keywords

  • AMS subject classification code (1991): 05C70

Fingerprint

Dive into the research topics of 'On packing bipartite graphs'. Together they form a unique fingerprint.

Cite this