## Abstract

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 C_{n} cycles. It is also proved that the two graphs G_{1} and G_{2} pack if 2ΔG_{1}G_{2}≯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 language | English (US) |
---|---|

Pages (from-to) | 167-169 |

Number of pages | 3 |

Journal | Combinatorics Probability and Computing |

Volume | 16 |

Issue number | 1 |

DOIs | |

State | Published - Jan 2007 |

## ASJC Scopus subject areas

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