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

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

Título:      Colorações de arestas que não contêm subgrafos 
             com um determinado padrão cromático 
            
Palestrante: Carlos Hoppen 
             Instituto de Matemática, UFRGS

Hora e Data: 14h, sexta-feira, 18 de julho de 2014

Local:       Sala Multi-usos do Numec

Resumo:

O problema que consideraremos  é motivado por uma questão de
Erdös e  Rothschild, proposta nos anos  70, sobre colorações
de arestas  que não  contêm cópias monocromáticas  de certos
subgrafos.   Tal questão  foi generalizada  por  Balogh para
colorações  de aresta  que  não contêm  subgrafos com  certa
coloração pré-fixada. Dado um  inteiro positivo r e um grafo
F,  um r-padrão P  de F  é uma  partição de  F em  r classes
(possivelmente  vazias), e  uma coloração  de arestas  de um
grafo G com  r cores é dita  livre de P se G  não contém uma
cópia  de  F  em  que  a partição  induzida  pela  coloração
coincide com P. Seja c_{r,(F,P)}(G) o número de r-colorações
de G livres  de P. O objetivo é  maximizar esse número entre
os grafos com  n vértices e descrever os  grafos que atingem
esse máximo. Nessa  palestra, apresentaremos uma perspectiva
histórica desse problema  e discutiremos resultados recentes
obtidos para diversas classes de grafos.

Trabalho conjunto com Fabrício Siqueira Benevides e Rudini
Menezes Sampaio (UFC), e Hanno Lefmann e Knut Odermann
(Technische Universität Chemnitz-Alemanha)