Informace o publikaci
Chromatic number for a generalization of Cartesian product graphs
| Autoři | |
|---|---|
| Rok publikování | 2009 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | Electronic Journal of Combinatorics |
| Citace | |
| Popis | 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 |