A note on the Grundy number and graph products

作者：Clarke Nancy E; Finbow Stephen; Fitzpatrick Shannon; Messinger Margaret Ellen^*; Milley Rebecca; Nowakowski Richard J

来源：Discrete Applied Mathematics, 2016, 202: 1-7.

DOI：10.1016/j.dam.2015.08.018

• Colouring
• Grundy
• Products

A proper colouring is referred to as a Grundy colouring, or first-fit colouring if every vertex has a neighbour from each of the colour classes lower than its own. The Grundy number of a graph is the maximum k (number of colours) such that a Grundy colouring exists.
In this note, we determine lower and upper bounds for the Grundy number of strong products of graphs, which lead to exact values for the product of some graph classes. We also provide an upper bound on the Grundy number of the strong product of n paths of length 2, which generalizes to an upper bound on the Grundy number of the strong product of n stars.

• 出版日期2016-3-31