============================================================
   Seminário de Teoria da Computaçăo e Combinatória (TCC)

============================================================

Título:      Minimum H-decompositions of graphs

            
Palestrante: Yury Person
             Humboldt-Universität zu Berlin

Hora e Data: 14h, sexta-feira, 17 de setembro de 2010

Local:       auditório do NUMEC

Resumo:


Let  phi_H(G) be  the  minimum number  of  graphs needed  to
partition  the   edge  set  of   G  into  edges   (K_2)  and
edge-disjoint copies of H. The  problem is what graph G on n
vertices maximizes phi_H(G)?

This  question was  asked by  Erdös, Goodman  and  Posa, who
showed that for H=K_3 the maximizer is the balanced complete
bipartite graph. Bollobás showed  that for H=K_r, r >= 3 the
only  maximizer  is the  Turán  graph.   Pikhurko and  Sousa
extended his  result for  general H with  chi(H)=r >=  3 and
proved  an   upper  bound  being   t_{r-1}(n)+o(n^2),  where
t_{r-1}(n) is  the  number  of edges in  (r-1)-partite Turán
graph   on   n  vertices.    They   also  conjectured   that
phi_H(G)=ex(n,H).

We verify  their conjecture  for edge-critical graphs  H, ie
those  graphs that contain  an edge,  such that  deleting it
chromatic number decreases. Moreover, we show  that the only
graph maximizing  phi_{H}(G) is  the Turán graph,  for large
n. Joint work with Lale Özkahya.