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

• Kenny Domingues UFC
• Yuri Silva de Oliveira UFC
• Ana Silva UFC https://orcid.org/0000-0001-8917-0564

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

Abstract

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.

Keywords: Greedy coloring, Partial Grundy coloring, Partial Grundy number, Lexicographic product of graphs

References

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.