Lower Bounds for the Partial Grundy Number of the Lexicographic Product of Graphs


A Grundy coloring of a graph $G$ is a coloring obtained by applying the greedy algorithm according to some order of the vertices of $G$. The Grundy number of $G$ is then the largest $k$ such that $G$ has a greedy coloring with $k$ colors. A partial Grundy coloring is a coloring where each color class contains at least one greedily colored vertex, and the partial Grundy number of $G$ is the largest $k$ for which $G$ has a partial greedy coloring. In this article, we give some results on the partial Grundy number of the lexicographic product of graphs, drawing a parallel with known results for the Grundy number.
Palavras-chave: Greedy coloring, Partial Grundy coloring, Partial Grundy number, Lexicographic product of graphs


Asté, M., Havet, F., and Linhares-Sales, C. (2010). Grundy number and products of graphs. Discrete Mathematics, 310(9):1482–1490.

Christen, C. A. and Selkow, S. M. (1979). Some perfect coloring properties of graphs. Journal of Combinatorial Theory, Series B, 27(1):49–59.

Erdős, P., Hedetniemi, S. T., Laskar, R. C., and Prins, G. C. (2003). On the equality ofthe partial grundy and upper ochromatic numbers of graphs. Discrete Mathematics, 272(1):53–64.

Geller, D. and Stahl, S. (1975). The chromatic number and other functions of the lexico-graphic product. Journal of Combinatorial Theory, Series B, 19(1):87–95.

Karp, R. M. (1972). Reducibility among Combinatorial problems, pages 85–103. Springer US.

Shi, Z., Goddard, W., Hedetniemi, S. T., Kennedy, K., Laskar, R., and McRae, A. (2005). An algorithm for partial grundy number on trees. Discrete Mathematics, 304(1-3):108–116.
Como Citar

Selecione um Formato
DOMINGUES, Kenny; OLIVEIRA, Yuri Silva de; SILVA, Ana. Lower Bounds for the Partial Grundy Number of the Lexicographic Product of Graphs. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 6. , 2021, Evento Online. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2021 . p. 42-45. ISSN 2595-6116. DOI: https://doi.org/10.5753/etc.2021.16376.