Busca avançada
Ano de início
Entree


The mod k chromatic index of random graphs

Texto completo
Autor(es):
Botler, Fabio ; Colucci, Lucas ; Kohayakawa, Yoshiharu
Número total de Autores: 3
Tipo de documento: Artigo Científico
Fonte: JOURNAL OF GRAPH THEORY; v. 103, n. 4, p. 13-pg., 2023-03-08.
Resumo

The mod k chromatic index of a graph G is the minimum number of colors needed to color the edges of G in a way that the subgraph spanned by the edges of each color has all degrees congruent to 1 (mod k). Recently, the authors proved that the mod k chromatic index of every graph is at most 198k - 101, improving, for large k, a result of Scott. Here we study the mod k chromatic index of random graphs. We prove that for every integer k >= 2, there is C-k > 0 such that if p >= C-k n(-1) log n and n (1 - p) -> infinity as n -> infinity, then the following holds: if k is odd, then the mod k chromatic index of G (n, p) is asymptotically almost surely (a.a.s.) equal to k, while if k is even, then the mod k chromatic index of G(2n, p) (respectively, G(2n + 1, p)) is a.a.s. equal to k (respectively, k + 1). (AU)

Processo FAPESP: 18/04876-1 - Teoria de Ramsey, teoria estrutural de grafos e aplicações em Bioinformática
Beneficiário:Guilherme Oliveira Mota
Modalidade de apoio: Auxílio à Pesquisa - Jovens Pesquisadores
Processo FAPESP: 20/08252-2 - Problemas extremais e probabilísticos em coloração de grafos
Beneficiário:Lucas Colucci Cavalcante de Souza
Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado
Processo FAPESP: 15/11937-9 - Investigação de problemas difíceis do ponto de vista algorítmico e estrutural
Beneficiário:Flávio Keidi Miyazawa
Modalidade de apoio: Auxílio à Pesquisa - Temático
Processo FAPESP: 19/13364-7 - Problemas extremais e estruturais em teoria dos grafos
Beneficiário:Cristina Gomes Fernandes
Modalidade de apoio: Auxílio à Pesquisa - Regular