Chromatic Number for a Generalization of Cartesian Product Graphs - Král’, Daniel; West, Douglas B. (The Electronic Journal of Combinatorics, 2009)
Let G be a class of graphs. A d-fold grid over G is a graph obtained from a d-dimensional rectangular grid of vertices by placing a graph from G on each of the lines parallel to one of the axes. Thus each vertex belongs to d of these subgraphs. The class of d-fold grids over G is denoted by G^d. Let f(G;d)=_GG^dχ(G). If each graph in G is k-colorable, then f(G;d)k^d. We show that this bound is best possible by proving that f(G;d)=k^d when G is the class of all k-colorable graphs. We also show that f(G;d)d6d floor when G is the class of graphs with at most one edge, and f(G;d)d6dfloor when G is the class of graphs with maximum degree 1.