Coloração caminho não repetitivo de ladders circulares

  • Fábio Botler UFRJ
  • Wanderson Lomenha UFRJ
  • João Pedro de Souza UFRJ / Colégio Pedro II

Resumo


Fixe uma coloração c : V (G) →  dos vértices de um grafo G e seja W = v1 · · · v2r um caminho em G. Dizemos que W é repetitivo (com respeito a c) se c(vi) = c(vi+r) para todo i ∈ [r]. Finalmente, dizemos que c é uma coloração caminho não-repetitiva de G se não existe caminho repetitivo em G, e denotamos por π(G) o menor número de cores em uma coloração caminho não-repetitiva de G. Nós estudamos o número cromático não repetitivo de ladders circulares. O k-ladder circular CLk é o grafo obtido de duas cópias v1 · · · vkv1 e u1 · · · uku1 do ciclo de ordem k pela adição do emparelhamento perfeito {viui : i ∈ [k]}. Neste artigo, mostramos que se k é par e k ≥ 36, então π(CLk) = 5.

Referências

Alon, N., Grytczuk, J. a., Hałuszczak, M., and Riordan, O. (2002). Nonrepetitive colorings of graphs. volume 21, pages 336–346. Random structures and algorithms (Poznan, 2001).

Botler, F., Lomenha, W., and de Souza, J. P. (2022). On the maximum number of edges in a graph with prescribed walk-nonrepetitive chromatic number. In Anais do VII Encontro de Teoria da Computação, pages 41–44. SBC.

Currie, J. D. (2002). There are ternary circular square-free words of length n for n ≥ 18. Electron. J. Combin., 9(1):Note 10, 7.

Rosenfeld, M. (2020). Another approach to non-repetitive colorings of graphs of bounded degree. Electron. J. Combin., 27(3):Paper No. 3.43, 16.

Thue, A. (1906). Über unendliche zeichenreihen. norske vid. Selsk. Skr. Mat. Nat. Kl, 7(1):22.

Wood, D. R. (2021). Nonrepetitive graph colouring. Electron. J. Combin., DS24(Dynamic Surveys):78.
Publicado
06/08/2023
BOTLER, Fábio; LOMENHA, Wanderson; SOUZA, João Pedro de. Coloração caminho não repetitivo de ladders circulares. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 8. , 2023, João Pessoa/PB. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2023 . p. 40-44. ISSN 2595-6116. DOI: https://doi.org/10.5753/etc.2023.229946.