Packing without some pieces

DOI10.4310/JOC.2019.V10.N1.A1zbMATH Open1401.05244arXiv1901.09185WikidataQ128833710 ScholiaQ128833710MaRDI QIDQ1630682FDOQ1630682

Authors: Raphael Yuster

Publication date: 10 December 2018

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

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.

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

Recommendations

zbMATH Keywords

edge-coloring packing avoidable graph

Mathematics Subject Classification ID

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)

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)