ملخص: In this paper, we give a relatively simple though very efficient way to color the d-dimensional grid G(n1,n2,…,nd) (with ni vertices in each dimension 1id), for two different types of vertex colorings: (1) acyclic coloring of graphs, in which we color the vertices such that (i) no two neighbors are assigned the same color and (ii) for any two colors i and j, the subgraph induced by the vertices colored i or j is acyclic; and (2) k-distance coloring of graphs, in which every vertex must be colored in such a way that two vertices lying at distance less than or equal to k must be assigned different colors. The minimum number of colors needed to acyclically color (respectively k-distance color) a graph G is called acyclic chromatic number of G (respectively k-distance chromatic number), and denoted a(G) (respectively k(G)). The method we propose for coloring the d-dimensional grid in those two variants relies on the representation of the vertices of Gd(n1,…,nd) thanks to its coordinates in each dimension; this gives us upper bounds on a(Gd(n1,…,nd)) and k(Gd(n1,…,nd)). We also give lower bounds on a(Gd(n1,…,nd)) and k(Gd(n1,…,nd)). In particular, we give a lower bound on a(G) for any graph G; surprisingly, as far as we know this result was never mentioned before. Applied to the d-dimensional grid Gd(n1,…,nd), the lower and upper bounds for a(Gd(n1,…,nd)) match (and thus give an optimal result) when the lengths in each dimension are "sufficiently large" (more precisely, if ). If this is not the case, then these bounds differ by an additive constant at most equal to . Concerning k(Gd(n1,…,nd)), we give exact results on its value for (1) k=2 and any d1, and (2) d=2 and any k1. In the case of acyclic coloring, we also apply our results to hypercubes of dimension d, Hd, which are a particular case of Gd(n1,…,nd) in which there are only 2 vertices in each dimension. In that case, the bounds we obtain differ by a multiplicative constant equal to 2.

لغة: إنجليزية