|
Description: |
Given graphs G and H, an H-decomposition of G is a partition of the edge set of
G such that each part is either a single edge or forms a graph isomorphic to H.
Let \phi_H(n) be the smallest number, \phi, such that any graph G of order n admits an
H-decomposition with at most \phi parts.
The exact computation of \phi_H(n) for an arbitrary H is still an open problem. Bollobás [Math. Proc. Cambridge Philosophical Soc. 79 (1976) 19-24] accomplished
this task for cliques. We will determine the asymptotic of \phi_H(n) for any fixed graph
H as n tends to infinity. When H is bipartite, we determine \phi_H(n) with a constant
additive error and provide an algorithm returning the exact value with running time
polynomial in log n.
This is joint work with Oleg Pikhurko, Carnegie Mellon University, USA. (pdf)
Area(s):
|
