Uma generalização do problema de Erdős-Rothschild para padrões de grafos completos

Abstract

A presente tese de doutorado trata de um problema extremal de coloração de arestas de grafos. Mais precisamente, nós trabalhamos em uma extensão do Problema de Erdős e Rothschild para padrões de grafos completos. Nosso principal resultado prova que, para n suficientemente grande e r ≥ r0(k, s, t), todo grafo G tem no máximo rtk−1(n) colorações que são livres de cópias de Kk coloridas com s ou mais cores. Além disso, mostramos que o único grafo que alcança este número de r-colorações é o grafo de Turán Tk−1(n). Como resultados parciais, demonstramos que para toda família PK de pares (Kk, P), onde P representa um padrão de Kk induzido por uma r-coloração, existe um grafo multipartido completo que é PK -extremal. Na sequência, mostramos que, sendo P(Kk ,≥s) a família de todos os padrões com s ou mais classes de um grafo completo Kk, todo grafo P(Kk ,≥s)-extremal deve ser multipartido completo. Também apresentamos, como parte da estratégia para a demonstração do resultado exato, a Propriedade de Estabilidade de Cores para grafos, a qual prova que grafos P(Kk ,≥s)-extremais que têm o número de r-colorações maior que rtk−1(n) devem ter uma estrutura “próxima”do grafo de Turán Tk−1(n). Pela forma como montamos a estratégia na prova da estabilidade de cores, obtivemos uma melhoria significativa para o parâmetro r0 em relação ao exigido por Hoppen, Lefmann e Odermann [26] para o padrão arco-íris, além de apresentar cotas inferiores para este parâmetro para todos os valores de 2 ≤ s < (k 2).

This thesis deals with an extremal problem of edge-colorings about graphs. More precisely, we worked on an extension of the Erdős–Rothschild Problem for complete graph patterns. Our main result proves that, for n large enough and r ≥ r0(k, s, t), every graph G has at most rtk−1(n) colorings that avoid copies of Kk colored with s or more colors. In addition to this, we show that the only graph that reaches this number of r-colorings is the Turán graph Tk−1(n). As partial results, we demonstrate that for any family PK of pairs (Kk, P ), where P represents a pattern of Kk induced by an r-coloring, there is a complete multipartite graph that is PK -extremal. We also we show that, if P(Kk ,≥s) is the family of all patterns of a complete graph Kk with s or more classes, every P(Kk ,≥s)-extremal graph must be complete multipartite. We also present, as part of the strategy for demonstrating the exact result, the Color Stability Property for graphs, which proves that P(Kk ,≥s)-extremal graphs must have a structure “close”to the Turán graph Tk−1(n). Due to the way we set up the strategy in the color stability, we obtained a significant improvement on the number of colors r0 in relation to the number required by Hoppen, Lefmann and Odermann [26] for the rainbow pattern. We also present lower bounds on this parameter for all values of 2 ≤ s < (k 2).