Chromatic number for a generalization of Cartesian product graphs
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.
- Coloring of the \(d^{\text{th}}\) power of the face-centered cubic grid
- Chromatic numbers and products
- Colourings of the Cartesian Product of Graphs and Multiplicative Sidon Sets
- scientific article; zbMATH DE number 5778120 (Why is no real title available?)
- On the chromatic number of the product of graphs
- Grid drawings and the chromatic number
- Graphs obtained from collections of blocks
This page was built for publication: Chromatic number for a generalization of Cartesian product graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2380225)
