tailieunhanh - Báo cáo toán học: "Chromatic number for a generalization of Cartesian product graphs"

Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Chromatic number for a generalization of Cartesian product graphs. | Chromatic number for a generalization of Cartesian product graphs Daniel Kral Institute for Theoretical Computer Science Faculty of Mathematics and Physics Charles University Prague Czech Republic Douglas B. Westt Mathematics Department University of Illinois Urbana IL west@ kral@ Submitted Aug 1 2008 Accepted Jun 7 2009 Published June 19 2009 Mathematics Subject Classification 05C05 Abstract 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 Gd. Let f G d maxGeợd x G . If each graph in G is k-colorable then f G d kd. We show that this bound is best possible by proving that f G d kd when G is the class of all k-colorable graphs. We also show that f G d ị_ự6l dgdj when G is the class of graphs with at most one edge and f G d _6l dgdj when G is the class of graphs with maximum degree 1. 1 Introduction The Cartesian product of graphs G1 . Gd is the graph with vertex set V G1 X X V Gd in which two vertices v1 . Vd and v1 . v d are adjacent if they agree in all but one coordinate and in the coordinate where they differ the values are adjacent The Institute for Theoretical Computer Science ITI is supported by the Ministry of Education of the Czech Republic as project 1M0545. This research was also partially supported by the grant GACR 201 09 0197. Research partially supported by the National Security Agency under Award No. H98230-06-1-0065. THE ELECTRONIC JOURNAL OF COMBINATORICS 16 2009 R71 1 vertices in the corresponding graph. The product can be viewed as a rectangular grid with copies of G1 . Gd placed on vertices forming lines parallel to the d axes. It is well-known and easy to show that the chromatic number of the Cartesian product of G1 . Gd is the maximum of the chromatic numbers of G1 . Gd 12 . In