Grundy number of graphs

Brice Effantin; Hamamache Kheddouci

Discussiones Mathematicae Graph Theory (2007)

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

Abstract

top
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.

How to cite

top

Brice 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. [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. [2] C.A. Christen and S.M. Selkow, Some perfect coloring properties of graphs, J. Combin. Theory B27 (1979) 49-59. Zbl0427.05033
  3. [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. [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. [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. [6] C. Germain and H. Kheddouci, Grundy coloring of powers of graphs, to appear in Discrete Math. 2006. 
  7. [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. [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. [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. [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. [11] A. McRae, NP-completeness Proof for Grundy Coloring, unpublished manuscript 1994. Personal communication. 
  12. [12] C. Parks and J. Rhyne, Grundy Coloring for Chessboard Graphs, Seventh North Carolina Mini-Conference on Graph Theory, Combinatorics, and Computing (2002). 
  13. [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. [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. [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. [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 ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.