Open Problem Garden

Importance: High ✭✭✭

Author(s):

Subject:	Graph Theory
	» Extremal Graph Theory

Keywords:

graph packing

Recomm. for undergrads: no

Posted	by:	asp
	on:	March 23rd, 2013

Conjecture (BEC-conjecture) If $G_1$ and $G_2$ are $n$ -vertex graphs and $(\Delta(G_1) + 1) (\Delta(G_2) + 1) < n + 1$ , then $G_1$ and $G_2$ pack.

A pair of $n$ -vertex graphs $G_1$ and $G_2$ are said to ${\it pack}$ if they are edge-disjoint subgraphs of the complete graph on $n$ vertices.

The main conjecture in the area of graph packing is the abovementioned conjecture by Bollobás, Eldridge [BE] and Catlin [C].

In support of the BEC-conjecture, Sauer and Spencer [SS] proved that if $G_1$ and $G_2$ are $n$ -vertex graphs and $2 \Delta(G_1) \Delta(G_2) < n$ then $G_1$ and $G_2$ pack.

Given a graph $G$ , $L(G)$ denotes the line graph of $G$ and $\Theta(G)$ denotes the number $\Delta(L(G)) + 2$ . Kostochka and Yu [KY1] proved that if $G_1$ and $G_2$ are two $n$ -vertex graphs with $\Theta(G_1) \Delta(G_2) \leq n$ , then $G_1$ and $G_2$ pack with the following exceptions: (1) $G_1$ is a perfect matching and $G_2$ is either $K_{n/2,n/2}$ with $n/2$ odd or contains $K_{n/2 + 1}$ or (2) $G_2$ is a perfect matching and $G_1$ is $K_{r,n-r}$ with $r$ odd or contains $K_{n/2 + 1}$ .

Kostachka and Yu [KY2] conjectured that if $G_1$ and $G_2$ are $n$ -vertex graphs with $\Theta(G_1) \Theta(G_2) < 2n$ then $G_1$ and $G_2$ pack.

Bibliography

*[BE] B. Bollabás and S. E. Eldridge, Maximal matchings in graphs with given maximal and minimal degrees, Congr. Numer. XV (1976), 165--168.

*[C] P. A. Catlin, Embedding subgraphs and coloring graphs under extremal degree conditions, Ph. D. Thesis, Ohio State Univ., Columbus (1976).

[KY1] A. V. Kostochka and G. Yu, An Ore-type analogue of the Sauer-Spencer Theorem, Graphs Combin. 23 (2007), 419--424.

[KY2] A. V. Kostochka and G. Yu, An Ore-type graph packing problems, Combin. Probab. Comput. 16 (2007), 167--169.

[SS] N. Sauer and J. Spencer, Edge disjoint placement of graphs, J. Combin. Theory Ser. B 25 (1978), 295--302.

* indicates original appearance(s) of problem.

add new comment

Open Problem Garden

Bibliography

Reply

Navigate

Recent Activity