A note on the Grundy number and graph 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...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2016-03, Vol.202, p.1-7
Main Authors: Clarke, Nancy E., Finbow, Stephen, Fitzpatrick, Shannon, Messinger, Margaret-Ellen, Milley, Rebecca, Nowakowski, Richard J.
Format: Article
Language:English
Subjects:
Color
Colour
Colouring
Graphs
Grundy
Mathematical analysis
Products
Stars
Upper bounds
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0166-218X
1872-6771
DOI:10.1016/j.dam.2015.08.018