A bandwidth theorem for approximate decompositions

Cited 4 time in webofscience Cited 0 time in scopus
  • Hit : 74
  • Download : 0
We provide a degree condition on a regular n-vertex graph G which ensures the existence of a near optimal packing of any family H of bounded degree n-vertex k-chromatic separable graphs into G. In general, this degree condition is best possible. Here a graph is separable if it has a sublinear separator whose removal results in a set of components of sublinear size. Equivalently, the separability condition can be replaced by that of having small bandwidth. Thus our result can be viewed as a version of the bandwidth theorem of Bottcher, Schacht and Taraz in the setting of approximate decompositions. More precisely, let delta k be the infimum over all delta > 1/2 ensuring an approximate Kk-decomposition of any sufficiently large regular n-vertex graph G of degree at least delta n. Now suppose that G is an n-vertex graph which is close to r-regular for some r >(delta k+o(1))n and suppose that H1,MIDLINE HORIZONTAL ELLIPSIS,Ht is a sequence of bounded degree n-vertex k-chromatic separable graphs with n-ary sumation ie(Hi)<=(1-o(1))e(G). We show that there is an edge-disjoint packing of H1,MIDLINE HORIZONTAL ELLIPSIS,Ht into G. If the Hi are bipartite, then r >(1/2+o(1))n is sufficient. In particular, this yields an approximate version of the tree packing conjecture in the setting of regular host graphs G of high degree. Similarly, our result implies approximate versions of the Oberwolfach problem, the Alspach problem and the existence of resolvable designs in the setting of regular host graphs of high degree.
Publisher
WILEY
Issue Date
2019-06
Language
English
Article Type
Article
Citation

PROCEEDINGS OF THE LONDON MATHEMATICAL SOCIETY, v.118, no.6, pp.1393 - 1449

ISSN
0024-6115
DOI
10.1112/plms.12218
URI
http://hdl.handle.net/10203/269975
Appears in Collection
MA-Journal Papers(저널논문)
Files in This Item
There are no files associated with this item.
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡ Click to see webofscience_button
⊙ Cited 4 items in WoS Click to see citing articles in records_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0