21/04/2017, 15:00 — 16:00 — Sala P3.10, Pavilhão de Matemática
Teresa Sousa, Escola Naval
Monochromatic edge decompositions of graphs
Let $H=(H_1, ..., H_k)$ be a fixed $k$-tuple of graphs and let $G$ be a graph on $n$ vertices whose edges are colored with $k$ colors. A monochromatic $H$-decomposition of $G$ is a partition of its edge set such that each part is either a single edge or a copy of $H_i$ monochromatic in color $i$. The aim is to find the smallest number, denoted by $f(n,H,k)$, such that, any $k$-edge colored graph with $n$ vertices admits a monochromatic $H$-decomposition with at most $f(n,H,k)$ parts. We will consider the problem when $H$ is a fixed $k$-tuple of cliques (a clique is a complete graph) for all values of $k$. The results presented will involve both the Turán numbers and the Ramsey numbers. This is joint work with Henry Liu and Oleg Pikhurko.