Download PDF - Grundy number of graphsAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

Grundy number of graphs

Authors 1, 1

Affiliations

  1. Laboratoire PRISMa, Université Claude Bernard Lyon 1, Bat. Nautibus (ex. 710), 843, Bd. du 11 novembre 1918, 69622 Villeurbanne Cedex, France

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.

Keywords

ENG
Grundy coloring, vertex coloring, cartesian product, graph product

Bibliography

  1. C.Y. Chang, W.E. Clark and E.O. Hare, Domination Numbers of Complete Grid Graphs, I, Ars Combinatoria 36 (1994) 97-111.
  2. C.A. Christen and S.M. Selkow, Some perfect coloring properties of graphs, J. Combin. Theory B27 (1979) 49-59.
  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.
  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.
  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.
  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.
  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.
  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.
  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.
  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.
  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.
  15. X. Zhu, Star chromatic numbers and products of graphs, J. Graph Theory 16 (1992) 557-569, doi: 10.1002/jgt.3190160604.
  16. X. Zhu, The fractional chromatic number of the direct product of graphs, Glasgow Mathematical Journal 44 (2002) 103-115, doi: 10.1017/S0017089502010066.
Discussiones Mathematicae Graph Theory
2007/27/1
Export to PBN, Opens in new tab
Pages:
5-18
Main language of publication
English
Received
2003-09-19
Accepted
2006-05-29
Published
2007

DOI: 10.7151/dmgt.1339

Exact and natural sciences