Coloração caminho não repetitivo de ladders circulares - Botler, Fábio; Lomenha, Wanderson; Souza, João Pedro de (Anais do Encontro de Teoria da Computação (ETC); 2023: Anais do VIII Encontro de Teoria da Computação, 2023)
Fixe uma coloração c : V (G) →  ℕ dos vértices de um grafo G e seja W = v 1 · · · 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 1 · · · v k v 1 e u 1 · · · u k u 1 do ciclo de ordem k pela adição do emparelhamento perfeito {v i u i : i ∈ [k]}. Neste artigo, mostramos que se k é par e k ≥ 36, então π(CL k ) = 5.