On the Partial Grundy Number of a Graph Minus a Matching

• Kenny Domingues UFC
• Ana Silva UFC

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

Resumo

Given a k-coloring S₁, . . . , S_k of G, a vertex in Si is said to be greedy if it has neighbors in S_j, for every j < i. Thus, a Grundy coloring can be seen as a coloring where every vertex is greedy. In contrast, a partial Grundy coloring is defined as a coloring in which each color class has at least one greedy vertex; the maximum number of colors in a partial Grundy coloring is denoted by ∂Γ(G). In this paper, we investigate some conjectures about Grundy colorings, already known not to hold, adapted to partial Grundy colorings. We prove that, while two of them also do not hold, a third does. Namely, that given a graph G and a matching M of G, we have that ∂Γ(G) ≤ 2∂Γ(G − M).

Palavras-chave: Grundy coloring, Partial Grundy coloring

Referências

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

Balogh, J., Hartke, S. G., Liu, Q., and Yu, G. (2008). On the first-fit chromatic number of graphs. SIAM Journal on Discrete Mathematics, 22(3):887–900.

Campos, V., Gyárfás, A., Havet, F., Sales, C. L., and Maffray, F. (2012). New bounds on the Grundy number of products of graphs. Journal of Graph Theory, 71(1):78–88.

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

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

Karp, R. M. (1972). Reducibility among combinatorial problems. In Complexity of computer computations, pages 85–103. Springer.