New Bounds on the Grundy Number of Products of Graphs |
| |
Authors: | Victor Campos András Gyárfás Frédéric Havet Claudia Linhares Sales Frédéric Maffray |
| |
Institution: | 1. Department of Computer Science, Federal University Of Ceará, , Fortaleza, CE, Brazil;2. Computer and Automation Research Institute, Hungarian Academy of Sciences, , Budapest H‐1518, Hungary;3. Projet Mascotte, I3S (CNRS UNSA) and INRIA 2004 Route des Lucioles, , BP 93 06902 Sophia‐Antipolis Cedex, France;4. CNRS, Laboratoire G‐SCOP UMR 5272, Grenoble‐INP, UJF‐Grenoble 1, , Grenoble F‐38031, France |
| |
Abstract: | The Grundy number of a graph G is the largest k such that G has a greedy k‐coloring, that is, a coloring with k colors obtained by applying the greedy algorithm according to some ordering of the vertices of G. In this article, we give new bounds on the Grundy number of the product of two graphs. © 2011 Wiley Periodicals, Inc. J Graph Theory 71:78–88, 2012 |
| |
Keywords: | coloring product Grundy |
|
|