Importance: High ✭✭✭
Keywords: graph packing
Recomm. for undergrads: no
Posted by: asp
on: March 23rd, 2013

\begin{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. \end{conjecture}

% You may use many features of TeX, such as % arbitrary math (between $...$ and $$...$$) % \begin{theorem}...\end{theorem} environment, also works for question, problem, conjecture, ... % % Our special features: % Links to wikipedia: \Def {mathematics} or \Def[coloring]{Graph_coloring} % General web links: \href [The On-Line Encyclopedia of Integer Sequences]{}

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.


% Example: %*[B] Claude Berge, Farbung von Graphen, deren samtliche bzw. deren ungerade Kreise starr sind, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe 10 (1961), 114. % %[CRS] Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas: \arxiv[The strong perfect graph theorem]{math.CO/0212070}, % Ann. of Math. (2) 164 (2006), no. 1, 51--229. \MRhref{MR2233847} % % (Put an empty line between individual entries)

*[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.


Comments are limited to a maximum of 1000 characters.