Minimum Decompositions of Graphs
 
 
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):
Date:  2008-05-28
Start Time:   14:30
Speaker:  Teresa Sousa (CMA/Mat. FCTUNL)
Place:  5.5
Research Groups: -Algebra and Combinatorics
See more:   <Main>  
 
© Centre for Mathematics, University of Coimbra, funded by
Science and Technology Foundation
Powered by: rdOnWeb v1.4 | technical support