On the maximum number of edges in a graph with prescribed walk-nonrepetitive chromatic number

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

Resumo


Fix a coloring c: V(G) → N of the vertices of a graph G and let W=v_1 ... v_{2r} be a walk in G. We say that W is repetitive (with respect to c) if c(v_i) = c(v_{i+r}) for i = 1,..., r; and that W is boring if v_i=v_{i+r}, for every i = 1,...,r. Finally, we say that c is a walk-nonrepetitive coloring of G if every repetitive walk is boring, and we denote by σ(G) the walk-nonrepetitive chromatic number, i.e., the minimum number of colors in a walk-nonrepetitive coloring of G. In this paper we explore the maximum number of edges in a graph G with n vertices for which σ(G) = k, for k≥ 4. In [Barát and Wood 2008] it was shown that e(G) ≤ (1/2)(k -1)n. We prove that the corresponding extremal graph is unique. More specifically, we show that e(G) ≤ (1/2)(k -1)n if and only if G is a union of disjoint copies of K_k. We also show that this upper bound can be improved for connected graphs for the case k = 4: if G is a connected graph for which σ(G) = 4 and |V(G)| ≥ 5, then e(G) ≤ (4/3)|V(G)|.

Palavras-chave: nonrepetitive coloring, walk, extremal

Referências

Barát, J. and Wood, D. R. (2008). Notes on nonrepetitive graph colouring. The Electronic Journal of Combinatorics, 15, R99.

Rosenfeld, M. (2020). Another approach to non-repetitive colorings of graphs of bounded degree. The Electronic Journal of Combinatorics, 27(3), P3.43.

Wood, D. R. (2021). Nonrepetitive graph colouring. The Electronic Journal of Combinatorics, DS24.
Publicado
31/07/2022
BOTLER, Fábio; LOMENHA, Wanderson; SOUZA, João Pedro de. On the maximum number of edges in a graph with prescribed walk-nonrepetitive chromatic number. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 7. , 2022, Niterói. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2022 . p. 41-44. ISSN 2595-6116. DOI: https://doi.org/10.5753/etc.2022.222730.