First-Fit coloring of Cartesian product graphs and its defining sets


  • Manouchehr Zaker



Let the vertices of a Cartesian product graph $G\Box H$ be ordered by an ordering $\sigma$. By the First-Fit coloring of $(G\Box H, \sigma)$ we mean the vertex coloring procedure which scans the vertices according to the ordering $\sigma$ and for each vertex assigns the smallest available color. Let $FF(G\Box H,\sigma)$ be the number of colors used in this coloring. By introducing the concept of descent we obtain a sufficient condition to determine whether $FF(G\Box H,\sigma)=FF(G\Box H,\tau)$, where $\sigma$ and $\tau$ are arbitrary orders. We study and obtain some bounds for $FF(G\Box H,\sigma)$, where $\sigma$ is any quasi-lexicographic ordering. The First-Fit coloring of $(G\Box H, \sigma)$ does not always yield an optimum coloring. A greedy defining set of $(G\Box H, \sigma)$ is a subset $S$ of vertices in the graph together with a suitable pre-coloring of $S$ such that by fixing the colors of $S$ the First-Fit coloring of $(G\Box H, \sigma)$ yields an optimum coloring. We show that the First-Fit coloring and greedy defining sets of $G\Box H$ with respect to any quasi-lexicographic ordering (including the known lexicographic order) are all the same. We obtain upper and lower bounds for the smallest cardinality of a greedy defining set in $G\Box H$, including some extremal results for Latin squares.


M. Ast\'{e}, F. Havet, C. Linhares Sales, Grundy number and products of

graphs. Discrete Math. 310 (2010), 1482–-1490.

F, Aurenhammer, J. Hagauer, W. Imrich, Cartesian graph factorization at logarithmic cost per edge. Comput. Complexity 2 (1992), 331-–349.

J. Balogh, S. G. Hartke, Q. Liu, G. Yu, On the first-fit chromatic number

of graphs, SIAM J Discrete Math. 22 (3) (2008), 887-–900.

V. Campos, A. Gy\'{a}rf\'{a}s, F. Havet, C. Linhares Sales, F. Maffray, New bounds on the

Grundy number of products of graphs, J. Graph Theory 71 (2012), 78-–88.

D. Donovan, E. S. Mahmoodian, C. Ramsay, A. P. Street, Defining

sets in combinatorics: a survey, Surveys in combinatorics, 2003

(Bangor), 115--174, London Math. Soc. Lecture Note Ser., 307,

Cambridge Univ. Press, Cambridge (2003)

D. G. Hoffman, Jr. P. D. Johnson, Greedy colorings and the Grundy chromatic number of the $n$-cube.

Bull. ICA 26 (1999), 49-–57.

F. Havet, T. Kaiser, M. Stehlik, Grundy number of the Cartesian product

of a tree and a graph. unpublished.

J. van Rees, More greedy defining sets in Latin squares. Australas. J. Combin. 44 (2009), 183-–198.

M. Zaker, Greedy defining sets of graphs. Australas. J. Combin. 23 (2001), 231--235.

M. Zaker, Results on the Grundy chromatic number of graphs. Discrete Math. 306 (2006), 3166--3173.

M. Zaker, Greedy defining sets of Latin squares. Ars Combin. 89 (2008), 205--222.

M. Zaker, More results on greedy defining sets. Ars Combin. 114 (2014), 53--64.