Publication details
Chromatic number for a generalization of Cartesian product graphs
| Authors | |
|---|---|
| Year of publication | 2009 |
| Type | Article in Periodical |
| Magazine / Source | Electronic Journal of Combinatorics |
| Citation | |
| Description | 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) = max(G is an element of Gd) (chi)(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) >= [root D/6logd] when G is the class of graphs with at most one edge, and f(G;d)>= [d/6logd] when G is the class of graphs with maximum degree 1 |