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

Abstract

Fix a coloring c : V (G) → ℕ of the vertices of a graph G and let W = v₁ · · · v_2r be a path in G. We say that W is repetitive (with respect to c) if c(v_i) = c(v_i+r) for every i ∈ [r]. Finally, we say that c is a path-nonrepetitive coloring of G if there is no repetitive path in G, and we denote by π(G) the minimum number of colors in a path-nonrepetitive coloring of G. We study the path-nonrepetitive chromatic number of circular ladders. The k-circular ladder CL_k is the graph obtained from two copies v₁ · · · v_kv₁ and u₁ · · · u_ku₁ of the cycle of order k by adding the perfect matching {v_iu_i : i ∈ [k]}. In this paper, we show that if k is even and k ≥ 36, then π(CL_k) = 5.

References

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.