# Grundy number of graphs

Brice Effantin; Hamamache Kheddouci

Discussiones Mathematicae Graph Theory (2007)

- Volume: 27, Issue: 1, page 5-18
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topBrice Effantin, and Hamamache Kheddouci. "Grundy number of graphs." Discussiones Mathematicae Graph Theory 27.1 (2007): 5-18. <http://eudml.org/doc/270336>.

@article{BriceEffantin2007,

abstract = {The Grundy number of a graph G is the maximum number k of colors used to color the vertices of G such that the coloring is proper and every vertex x colored with color i, 1 ≤ i ≤ k, is adjacent to (i-1) vertices colored with each color j, 1 ≤ j ≤ i -1. In this paper we give bounds for the Grundy number of some graphs and cartesian products of graphs. In particular, we determine an exact value of this parameter for n-dimensional meshes and some n-dimensional toroidal meshes. Finally, we present an algorithm to generate all graphs for a given Grundy number.},

author = {Brice Effantin, Hamamache Kheddouci},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {Grundy coloring; vertex coloring; cartesian product; graph product; meshes; algorithm},

language = {eng},

number = {1},

pages = {5-18},

title = {Grundy number of graphs},

url = {http://eudml.org/doc/270336},

volume = {27},

year = {2007},

}

TY - JOUR

AU - Brice Effantin

AU - Hamamache Kheddouci

TI - Grundy number of graphs

JO - Discussiones Mathematicae Graph Theory

PY - 2007

VL - 27

IS - 1

SP - 5

EP - 18

AB - The Grundy number of a graph G is the maximum number k of colors used to color the vertices of G such that the coloring is proper and every vertex x colored with color i, 1 ≤ i ≤ k, is adjacent to (i-1) vertices colored with each color j, 1 ≤ j ≤ i -1. In this paper we give bounds for the Grundy number of some graphs and cartesian products of graphs. In particular, we determine an exact value of this parameter for n-dimensional meshes and some n-dimensional toroidal meshes. Finally, we present an algorithm to generate all graphs for a given Grundy number.

LA - eng

KW - Grundy coloring; vertex coloring; cartesian product; graph product; meshes; algorithm

UR - http://eudml.org/doc/270336

ER -

## References

top- [1] C.Y. Chang, W.E. Clark and E.O. Hare, Domination Numbers of Complete Grid Graphs, I, Ars Combinatoria 36 (1994) 97-111. Zbl0818.05038
- [2] C.A. Christen and S.M. Selkow, Some perfect coloring properties of graphs, J. Combin. Theory B27 (1979) 49-59. Zbl0427.05033
- [3] N. Cizek and S. Klavžar, On the chromatic number of the lexicographic product and the cartesian sum of graphs, Discrete Math. 134 (1994) 17-24, doi: 10.1016/0012-365X(93)E0056-A. Zbl0815.05030
- [4] J.E. Dunbar, S.M. Hedetniemi, S.T. Hedetniemi, D.P. Jacobs, J. Knisely, R.C. Laskar and D.F. Rall, Fall Colorings of Graphs, J. Combin. Math. and Combin. Computing 33 (2000) 257-273. Zbl0962.05020
- [5] C. Germain and H. Kheddouci, Grundy coloring for power caterpillars, Proceedings of International Optimization Conference INOC 2003, 243-247, October 2003 Evry/Paris France. Zbl1259.05059
- [6] C. Germain and H. Kheddouci, Grundy coloring of powers of graphs, to appear in Discrete Math. 2006.
- [7] S. Gravier, Total domination number of grid graphs, Discrete Appl. Math. 121 (2002) 119-128, doi: 10.1016/S0166-218X(01)00297-9. Zbl0995.05109
- [8] S.M. Hedetniemi, S.T. Hedetniemi and T. Beyer, A linear algorithm for the Grundy (coloring) number of a tree, Congr. Numer. 36 (1982) 351-363. Zbl0507.68038
- [9] J.D. Horton and W.D. Wallis, Factoring the cartesian product of a cubic graph and a triangle, Discrete Math. 259 (2002) 137-146, doi: 10.1016/S0012-365X(02)00376-X. Zbl1008.05120
- [10] M. Kouider and M. Mahéo, Some bound for the b-chromatic number of a graph, Discrete Math. 256 (2002) 267-277, doi: 10.1016/S0012-365X(01)00469-1. Zbl1008.05056
- [11] A. McRae, NP-completeness Proof for Grundy Coloring, unpublished manuscript 1994. Personal communication.
- [12] C. Parks and J. Rhyne, Grundy Coloring for Chessboard Graphs, Seventh North Carolina Mini-Conference on Graph Theory, Combinatorics, and Computing (2002).
- [13] F. Ruskey and J. Sawada, Bent Hamilton Cycles in d-Dimensional Grid Graphs, The Electronic Journal of Combinatorics 10 (2003) #R1. Zbl1012.05105
- [14] J.A. Telle and A. Proskurowski, Algorithms for vertex partitioning problems on partial k-trees, SIAM J. Discrete Math. 10 (4) (1997) 529-550, doi: 10.1137/S0895480194275825. Zbl0885.68118
- [15] X. Zhu, Star chromatic numbers and products of graphs, J. Graph Theory 16 (1992) 557-569, doi: 10.1002/jgt.3190160604. Zbl0766.05033
- [16] X. Zhu, The fractional chromatic number of the direct product of graphs, Glasgow Mathematical Journal 44 (2002) 103-115, doi: 10.1017/S0017089502010066. Zbl0995.05052

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.