✦ LIBER ✦

Packing graphs with odd and even trees

✍ Scribed by P. C. Fishburn

Publisher: John Wiley and Sons
Year: 1983
Tongue: English
Weight: 643 KB
Volume: 7
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190070309

No coin nor oath required. For personal study only.

✦ Synopsis

The Gyarfas-Lehel tree-packing conjecture asserts that any sequence T,, T,, ..., Tn-l of trees with 1, 2, ..., n -1 edges packs into the complete graph K, on n vertices. The present paper examines two conjectures that jointly imply the Gydrfas-Lehel conjecture:

For n even, any TI, T 3 , . . ., T,-I pack into the half-complete graph 2. For n odd, any T,, T 4 , ..., T n -l pack into the half-complete graph H , on n vertices.

H , on n vertices.

The H , are uniquely defined by their degree sequences: H , and are complements in K , , , . It is shown that H , and T,+l pack into H , , , if T,,+l is a double star, unimodal triple star, interior-3 caterpillar, or scorpion. Hence Conjectures 1 and 2 are true for these specialized types of trees. The conjectures are also valid for all trees when n s 9, so that the Gyarfas-Lehel conjecture holds for n C 9.

📜 SIMILAR VOLUMES

Packing and Decomposition of Graphs with

Packing and Decomposition of Graphs with Trees

✍ Raphael Yuster 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 214 KB

Let H be a tree on h 2 vertices. It is shown that if n is sufficiently large and G=(V, E ) is an n-vertex graph with $(G) wnÂ2x , then there are w |E |Â(h&1)x edge-disjoint subgraphs of G which are isomorphic to H. In particular, if h&1 divides |E | then there is an H-decomposition of G. This result

Packing trees into planar graphs

✍ A. García; C. Hernando; F. Hurtado; M. Noy; J. Tejel 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 108 KB

## Abstract In this study, we provide methods for drawing a tree with __n__ vertices on a convex polygon, without crossings and using the minimum number of edges of the polygon. We apply the results to obtain planar packings of two trees in some specific cases. © 2002 Wiley Periodicals, Inc. J Grap

Even and odd holes in cap-free graphs

✍ Conforti, Michele; Cornu�jols, G�rard; Kapoor, Ajai; Vu?kovi?, Kristina 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 158 KB 👁 1 views

It is an old problem in graph theory to test whether a graph contains a chordless cycle of length greater than three (hole) with a specific parity (even, odd). Studying the structure of graphs without odd holes has obvious implications for Berge's strong perfect graph conjecture that states that a g

Packing a tree with a graph of the same

Packing a tree with a graph of the same size

✍ P. J. Slater; S. K. Teo; H. P. Yap 📂 Article 📅 1985 🏛 John Wiley and Sons 🌐 English ⚖ 195 KB

## Abstract We prove that if __T__ is a tree of order __p__ ⩾ 5 and __G__ is a graph of order __p__ and size __p__ ‐ 1 such that neither __T__ nor __G__ is a star, then __T__ can be embedded in G, the complement of __G__.

Trees and unicyclic graphs with hamilton

Trees and unicyclic graphs with hamiltonian path graphs

✍ Xingxing Yu 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 154 KB

## Abstract We prove two conjectures of Broersma and Hoede about path graphs of trees and unicyclic graphs.

K4-free graphs with no odd hole: Even pa

K4-free graphs with no odd hole: Even pairs and the circular chromatic number

✍ Yori Zwols 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 219 KB

An odd hole in a graph is an induced cycle of odd length at least five. In this article we show that every imperfect K 4 -free graph with no odd hole either is one of two basic graphs, or has an even pair or a clique cutset. We use this result to show that every K 4 -free graph with no odd hole has