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

DOI: https://doi.org/10.5753/etc.2023.229946

Resumo

Fixe uma coloração c : V (G) → ℕ dos vértices de um grafo G e seja W = v₁ · · · v_2r um caminho em G. Dizemos que W é repetitivo (com respeito a c) se c(v_i) = c(v_i+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 CL_k é o grafo obtido de duas cópias v₁ · · · v_kv₁ e u₁ · · · u_ku₁ do ciclo de ordem k pela adição do emparelhamento perfeito {v_iu_i : i ∈ [k]}. Neste artigo, mostramos que se k é par e k ≥ 36, então π(CL_k) = 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.