An ore-type analogue of the sauer-spencer theorem

Research output: Contribution to journalArticlepeer-review

Abstract

Two graphs G 1 and G 2 of order n pack if there exist injective mappings of their vertex sets into [n], such that the images of the edge sets do not intersect. Sauer and Spencer proved that if Δ (G 1) Δ (G 2) < 0.5n, then G 1 and G 2 pack. In this note, we study an Ore-type analogue of the Sauer-Spencer Theorem. Let θ(G) = max{d(u) + d(v): uv E(G)}. We show that if θ(G 1)Δ(G 2) < n, then G 1 and G 2 pack. We also characterize the pairs (G 1,G 2) of n-vertex graphs satisfying θ(G 1)Δ(G 2) = n that do not pack.

Original languageEnglish (US)
Pages (from-to)419-424
Number of pages6
JournalGraphs and Combinatorics
Volume23
Issue number4
DOIs
StatePublished - Aug 2007

Keywords

  • Graph packing
  • Ore-type conditions

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint Dive into the research topics of 'An ore-type analogue of the sauer-spencer theorem'. Together they form a unique fingerprint.

Cite this