Lower Bounds for the Partial Grundy Number of the Lexicographic Product of Graphs
ResumoA 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.
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.