Open AccessLower Bounds for the Partial Grundy Number of the Lexicographic Product of Graphs
Author(s) -
Kenny Domingues,
Yuri Silva de Oliveira,
Ana Silva
Publication year - 2021
Language(s) - English
Resource type - Conference proceedings
DOI - 10.5753/etc.2021.16376
Subject(s) - combinatorics , greedy coloring , lexicographical order , vertex (graph theory) , fractional coloring , mathematics , graph coloring , colored , complete coloring , list coloring , graph , greedy algorithm , edge coloring , product (mathematics) , discrete mathematics , graph power , algorithm , geometry , materials science , line graph , composite material
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.