Publication details

Chromatic number for a generalization of Cartesian product graphs

Authors

KRÁĽ Daniel WEST DB

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

You are running an old browser version. We recommend updating your browser to its latest version.

More info