Packing without some pieces

DOI10.4310/JOC.2019.V10.N1.A1MaRDI QIDQ1630682zbMATH OpenWikidataFDO

Publication date 10 December 2018

Published in Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1901.09185

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

Abstract: ErdH{o}s and Hanani proved that for every fixed integer

k g e 2

, the complete graph

K_{n}

can be almost completely packed with copies of

K_{k}

; that is,

K_{n}

contains pairwise edge-disjoint copies of

K_{k}

that cover all but an

o_{n} (1)

fraction of its edges. Equivalently, elements of the set

C (k)

of all red-blue edge colorings of

K_{k}

can be used to almost completely pack every red-blue edge coloring of

K_{n}

. The following strengthening of the aforementioned ErdH{o}s-Hanani result is considered. Suppose

C^{'} s u b s e t C (k)

. Is it true that we can use elements only from

C^{'}

and almost completely pack every red-blue edge coloring of

K_{n}

? An element

C i n C (k)

is {em avoidable} if

C^{'} = C (k) s e t m i n u s C

has this property and a subset

c a l F s u b s e t C (k)

is avoidable if

C^{'} = C (k) s e t m i n u s c a l F

has this property. It seems difficult to determine all avoidable graphs as well as all avoidable families. We prove some nontrivial sufficient conditions for avoidability. Our proofs imply, in particular, that (i) almost all elements of

C (k)

are avoidable (ii) all Eulerian elements of

C (k)

are avoidable and, in fact, the set of all Eulerian elements of

C (k)

is avoidable.

Recommendations

This page was built for publication: Packing without some pieces

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