The Bollob\'as-Eldridge-Catlin conjecture for even girth at least 10

arXiv1703.05149MaRDI QIDQ6284358FDOQ6284358

Ross J. Kang, Wouter Cames van Batenburg

Publication date: 15 March 2017

Abstract: Two graphs

G_{1}

and

G_{2}

on

n

vertices are said to extit{pack} if there exist injective mappings of their vertex sets into

[n]

such that the images of their edge sets are disjoint. A longstanding conjecture due to Bollob'as and Eldridge and, independently, Catlin, asserts that, if

(D e l t a (G_{1}) + 1) (D e l t a (G_{2}) + 1) l e n + 1

, then

G_{1}

and

G_{2}

pack. We consider the validity of this assertion under the additional assumptions that neither

G_{1}

nor

G_{2}

contain a

4

-,

6

- or

8

-cycle, and that

D e l t a (G_{1})

or

D e l t a (G_{2})

is large enough (

g e 940060

).

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

This page was built for publication: The Bollob\'as-Eldridge-Catlin conjecture for even girth at least $10$

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6284358)