Um limiar para a quantidade de 3-colorações de Gallai em G(n,p)

• Ano de defesa: 2021
• Autor(a) principal: Monteiro, Rubens Cainan Sabóia
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Palavras-chave em Português: Coloração de grafo; Combinatória extremal; Colorações de arestas; Regularidade esparsa; Graph coloring; Extremal combinatorics; Edge colorings; Sparse regularity
• Link de acesso: http://www.repositorio.ufc.br/handle/riufc/63318

We study the number of Gallai 3-colorings in the Erdös-Rényi random graph, G(n, p). A Gallai 3-coloring of a graph is a coloring of its edges with colors {1,2,3} such that there is no rainbow triangle, that is, a triangle with edges of 3 distinct colors. It is trivial that for any graph with E edges, the number of Gallai 3-colorings is between 2E and 3E. Now, let E be the random variable for the number of edges in G(n, p). We show that for every δ > 0 there are constants cand C such that, asymptotically almost surely, for p < cn−1/2, the number of Gallai 3-coloring of G(n, p) is at least 3(1−δ)E; and for p > Cn−1/2 this number is at most 2(1+δ)E.