Ore-type graph packing problems

Research output: Contribution to journalArticlepeer-review


The solution to Dirack and Ore-type graph packing problems is presented. For any n-vertex graph G with an assigned maximum degree then G packs with a cycle of length n. The generalization of Dirac's theorem to packing of general graphs states that for a natural number greater than or equal to 3 and G an n-vertex graph with maximum edge-average degree smaller than 3, then G has Cn cycles. It is also proved that the two graphs G1 and G2 pack if 2ΔG1G2≯n. The maximum edge-average degree of a graph is related to the maximum degree of the line graph L(G), and any bound on maximum edge-average degree is a bound on Δ(L(G)). Ore-type analogue states that every graph G has two graphs pack for an equitable coloring with k colors for any k≥maximum edge-average degree.

Original languageEnglish (US)
Pages (from-to)167-169
Number of pages3
JournalCombinatorics Probability and Computing
Issue number1
StatePublished - Jan 2007

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Statistics and Probability
  • Computational Theory and Mathematics
  • Applied Mathematics


Dive into the research topics of 'Ore-type graph packing problems'. Together they form a unique fingerprint.

Cite this