Chromatic number for a generalization of Cartesian product graphs (Q2380225)

Summary: Let \({\mathcal G}\) be a class of graphs. A \(d\)-fold grid over \({\mathcal G}\) is a graph obtained from a \(d\)-dimensional rectangular grid of vertices by placing a graph from \({\mathcal 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 \({\mathcal G}\) is denoted by \({\mathcal G}^d\). Let \(f({\mathcal G};d)= \max_{G\in{\mathcal G}^d}(G)\). If each graph in \({\mathcal G}\) is \(k\)-colorable, then \(f({\mathcal G};d)\leq k^d\). We show that this bound is best possible by proving that \(f({\mathcal G};d)= k^d\) when \({\mathcal G}\) is the class of all \(k\)-colorable graphs. We also show that \(f({\mathcal G};d)\geq \left\lfloor \sqrt{\frac{d}{6\log d}}\right\rfloor\) when \({\mathcal G}\) is the class of graphs with at most one edge, and \(f({\mathcal G};d)\geq \lfloor \frac{d}{6\log d}\rfloor\) when \({\mathcal G}\) is the class of graphs with maximum degree 1.