Limitantes para o número de colorações das arestas de Kn que não possuem um K4-Rainbow.

Detalhes bibliográficos
Ano de defesa:	2025
Autor(a) principal:	Ribeiro, Rodrigo Fernandes
Orientador(a):	Não Informado pela instituição
Banca de defesa:	Não Informado pela instituição
Tipo de documento:	Dissertação
Tipo de acesso:	Acesso aberto
Idioma:	por
Instituição de defesa:	Não Informado pela instituição
Programa de Pós-Graduação:	Não Informado pela instituição
Departamento:	Não Informado pela instituição
País:	Não Informado pela instituição
Palavras-chave em Português:	Combinatória extremal Grafos Contagem Colorações de Gallai Extremal combinatorics Graphs Counting Gallai colorings CNPQ::CIENCIAS EXATAS E DA TERRA::MATEMATICA::MATEMATICA APLICADA::MATEMATICA DISCRETA E COMBINATORIA
Link de acesso:	http://repositorio.ufc.br/handle/riufc/79986
Resumo:	Given n,r ∈ N, this paper seeks non-trivial lower and upper bounds for the number of r-edge colorings, of the complete graph Kn, that avoid K4-rainbow (K4 colored in such a way that if an edge is colored with a color λ, another edge can’t be colored by λ) as a subgraph. We denote this number of colorings by c4(n,r) and prove that, if n ≥ 3, then c4(n,r) ≥ max{5(2n),r1+⌊n2 /4 ⌋. We also demonstrate that, fixed r > 5y, with y ≥ 10, for n large enough, c4(n,r) ≤ r ^Ä 1+o(1)+y−91 ä n2 /4 .

Registros relacionados