ARS MATHEMATICA CONTEMPORANEA Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.) ARS MATHEMATICA CONTEMPORANEA 9 (2015) 321-344 Subdivision into ¿-packings and S-packing chromatic number of some lattices Nicolas Gastineau * LE2I, UMR CNRS 6306, Université de Bourgogne, 21078 Dijon, France Hamamache Kheddouci Université de Lyon, CNRS, Université Lyon 1, LIRIS, UMR5205, F-69622, France Olivier Togni LE2I, UMR CNRS 6306, Université de Bourgogne, 21078 Dijon, France Received 30 January 2013, accepted 3 June 2015, published online 7 August 2015 An ¿-packing in a graph G is a set of vertices at pairwise distance greater than i. For a nondecreasing sequence of integers S = (si, s2,...), the S-packing chromatic number of a graph G is the least integer k such that there exists a coloring of G into k colors where each set of vertices colored i, i = 1,..., k, is an sj-packing. This paper describes various subdivisions of an ¿-packing into j -packings (j > i) for the hexagonal, square and triangular lattices. These results allow us to bound the S-packing chromatic number for these graphs, with more precise bounds and exact values for sequences S = (sj,i G N*), Sj = d + L(i - 1)/nJ. Keywords: Packing chromatic number, i-packing, hexagonal lattice, square lattice, triangular lattice, distance coloring. Math. Subj. Class.: 05C15, 05C63, 05C70. 1 Introduction Let G = (V, E) be a (finite or infinite) graph and let N(u) = {v G V(G) | uv G E(G)} be the set of neighbors of vertex u. A set X Ç V(G) is an ¿-packing if for any distinct pair u, v G Xi, d(u, v) > i, where d(u, v) denotes the usual shortest path distance between u and * Partially supported by the Burgundy Council and the Rhône-Alpes Council. E-mail addresses: Nicolas.Gastineau@u-bourgogne.fr (Nicolas Gastineau), hamamache.kheddouci@univ-lyon1.fr (Hamamache Kheddouci), Olivier.Togni@u-bourgogne.fr (Olivier Togni) ©® This work is licensed under http://creativecommons.org/licenses/by/3.0/ Abstract 322 Ars Math. Contemp. 9 (2015) 165-186 v. We will use Xj to refer to an ¿-packing in a graph G. A k-coloring c of G is a map from V(G) to {1,..., k} such that for every pair of adjacent vertices (u, v), we have c(u) = c(v). For a graph G and a k-coloring c of G, let cj be {u G V(G) | c(u) = i}. The smallest integer k such that there exists a k-coloring of G for which for every i, with 1 < i < k, cj is a i-packing, is called the packing chromatic number of G and is denoted by xP(G). This concept was introduced by Goddard et al. [7] under the name of broadcast chromatic number. More generally, for a nondecreasing sequence of integers S = (si, s2,...), an S-packing k-coloring is a k-coloring c of V(G) such that for every i, with 1 < i < k, cj is a sj-packing. Such a coloring will also simply be called an (s1,..., sk)-coloring. The S-packing chromatic number of G denoted by xS (G), is the smallest k such that G admits an S-packing k-coloring. For the sequences S = (sj, i G N*), with sj = d + [(i - 1)/nJ, we call xSP (G) the (d, n)-packing chromatic number and denote it by xp'n(G). For any connected graph G such that |V(G)| > d +1, xdP'n(G) > d +1 and xp'1(G) = Xp(G). For every bipartite graph G, xi'2 (G) =2 (a bipartite graph is 2-colorable). Moreover, the smallest n such that xp'n(G) = n corresponds to the d-distant chromatic number [12], i.e. the minimum number of d-packings that form a partition of the vertices. Let denote the two-way infinite path, let Z2 = denote the planar square lattice (where □ is the Cartesian product), t denote the planar triangular lattice and h denote the planar hexagonal lattice. In this article, for an (s1, s2,...)-coloring of a graph, we prefer to map vertices to the color multiset {s1, s2,...} even if two colors can then be denoted by the same number. This notation allows the reader to directly see to which type of packing the vertex belong depending on its color. When needed, we will denote colors of vertices in different i-packings by ia, ib,.... 1.1 Motivation and related work Packing colorings in graphs are inspired from frequency planning in wireless systems. The concept of S-packing coloring emphasizes the fact that signals can have different powers similar to the packing coloring but enables the presence of several signals with the same power, providing a more realistic model for the frequency assignment problem. The packing chromatic number of lattices has been studied by several authors: Soukal and Holub [13] proved that Xp(Z2) < 17, Ekstein et al. [1] that 12 < Xp(Z2); Fiala et al. [4] showed that Xp(h) < 7, Xp(Z2^) = to and Xp(h^Pe) = ^ and Finbow and Rall [5] proved that xp(T) = to. S-packing colorings with sequences S other than (1,2,..., k) first appear in [7, 3]. Goddard and Xu [8] have recently studied S-packing colorings for the infinite path and for square and triangular lattices, determining conditions on the first elements of the sequence for which the graph is or is not S-packing-colorable. Regarding the complexity, Goddard et al. [7] proved that the problem of (1,2,3)-packing coloring is polynomial while (1, 2, 3,4)-packing coloring and (1, 2, 2)-packing coloring are NP-complete. Fiala and Golovach [3] showed that the problem of (1,2,..., k)-coloring is NP-complete for trees. The NP-completeness of (1,1, 2)-coloring was proved by Goddard and Xu [9] and afterward by Gastineau [6]. While the packing coloring corresponds to an S-packing coloring with a strictly increasing sequence and the d-distant chromatic number corresponds to a constant one, the sequence in the (d, n)-packing coloring also tends to infinity, but the parameter n allows us to control its growth. N. Gastineau andH. Kheddouci: Subdivision into i-packings and S-packing chromatic number... 323 d\n 1 2 3 4 5 6 1 7 [4, 11] 2 2 2 2 2 2 TO 5-8 5 4 4 4 3 TO 15-35 9- 13 8 - 10 7-8 6 4 TO 61 - ? 20-58 15-27 13-21 12- 18 5 TO TO 37-? 25-? 21 - ? 19- ? 8 TO TO TO ? ? ? 11 TO TO TO TO ? ? 13 TO TO TO TO TO ? 16 TO TO TO TO TO TO Table 1: Bounds for (d, n)-packing chromatic numbers of the hexagonal lattice. Moreover, one can note that all the S-packing colorings of square and hexagonal lattices published so far have the property that the si-packing is maximum and the other si -packings are obtained by subdivisions of s1-packings (and are not always maximum). Therefore, we find it interesting to study subdivision of an ¿-packing into j -packings, j > i, in lattices. These subdivisions can in turn be used to describe patterns to obtain an S-packing coloring of a lattice. However, determining the families of graphs G for which for any S such that G is S-colorable, the S-coloring satisfies the above property remains an open question. Recently Goddard and Xu [8] proved that there exist nondecreasing sequences S such that P» is S-colorable and in any (s1,..., \SP (P»))-packing coloring of P», the s 1 -packing is not maximum, showing that for P», there are sequences S for which the above property is not satisfied. 1.2 Our results The second section introduces some definitions and results related to density. The third section introduces some subdivision of the lattices into i-packings. The fourth and fifth sections give lower bounds resulting from Section 2 and upper bounds resulting from Section 3 for the S-packing chromatic number and the (d, n)-packing chromatic number of the lattices h, Z2 and t. Tables 1, 2 and 3 summarize the values obtained in this paper for the (d, n)-packing chromatic number, giving an idea of our results. The emphasized numbers are exact values and all pairs of values are lower and upper bounds. Lower bounds have been calculated from Proposition 2.2 and Propositions 2.5, 2.7 and 2.9. Some of the results for square and triangular lattice have been found independently by Goddard and Xu [8]. 2 Density of i-packings 2.1 Density of an i-packing in a lattice Let G = (V, E) be a graph, finite or infinite and let n be a positive integer. For a vertex x of G, the ball of radius n centered at x is the set Bn(x) = {v G V(G)|dG(x, v) < n} and the sphere of radius n centered at x is the set dBn(x) = {v G V(G) |dG(x, v) = n}. The density of a set of vertices X C V(G) is d(X) = limsupmax{ }| }. The notion of k-area was introduced by Fiala et al. [4]. We propose here a slightly modified 324 Ars Math. Contemp. 9 (2015) 165-186 d\n 1 2 3 4 5 6 1 12-17 [1, 13] 2 2 2 2 2 2 TO 11-20 7-8 6 [8] 5 [8] 5 3 TO 57 - ? 16-33 12-20 10-17 10- 14 4 TO TO 44- ? 25-56 20-34 18-28 5 TO TO 199- ? 50- ? 35-? 29-? 6 TO TO TO ? ? ? 8 TO TO TO TO ? ? 10 TO TO TO TO TO ? 12 TO TO TO TO TO TO Table 2: Bounds for (d, n)-packing chromatic numbers of the square lattice. d\n 1 2 3 4 5 6 1 to [5] 5 - 6 [8] 3 3 3 3 2 TO 127-? 14- ? 10-16 9 - 13 8 - 10 3 TO TO 81 - ? 28-72 20-38 17-26 4 TO TO TO 104- ? 49 - ? 36- ? 5 TO TO TO TO ? ? 7 TO TO TO TO TO ? 8 TO TO TO TO TO TO Table 3: Bounds for (d, n)-packing chromatic numbers of the triangular lattice. N. Gastineau andH. Kheddouci: Subdivision into i-packings and S-packing chromatic number... 325 A(2)=7 A(1)=3 Figure 1: Examples of k-area in t. definition: Definition 2.1. Let G be a graph, x G V(G), and let k be a positive integer. The k-area A(x, k) assigned to G is defined by : |Bk/2(x)| for k even; A(x,k)=< |B[fc/2J(x)| + E IN(")nBLfc/2j(x)|+|N(^r^)^2 for k odd. deg(u) For vertex-transitive graphs, the k-areas are the same for all vertices, hence we denote it by A(k). The motivation for our modification of the notion of k-area with the introduction of the set of neighbors inside the sphere is to have sharper density bounds than the ones obtained by the initial notion of k-area. For the square and the hexagonal lattice the notion coincide as the relation is empty. However, for the triangular lattice, the density bound is smaller: the definition of Fiala et al. [4] gives A(1) = 2 whereas A(1) = 3 in our case since there are adjacent vertices in the sphere (as for every u g dBi(x), |N(u) n dBi(x)|/2 = 1, then it adds one to the initial definition of k-area). Figure 1 illustrates this example giving a coverage of the triangular lattice by balls of radius 1. In one case (on the left) the balls are disjoint and in the second case (on the right) each sphere can be shared by several balls. Observe that in the second case, each vertex u in a sphere centered at x has two neighbors, and hence |N(u) n dB1(x)|/2= 1. Proposition 2.2. Let G be a vertex-transitive graph with finite degree, and i be a positive integer. If Xi is an i-packing in G, then d(Xi) < 1 A(i)' Proof. Observe that for arbitrary vertices x and y of an i-packing Xi, the sets B\i/2j (x) and Blj/2j (y) are disjoint, since the vertices x and y are at distance greater than i. Then d(Xi) < 1/|B^/2j (x)|. Assume that i is an odd number and let u be a vertex at distance [i/2] from x, then u has deg(u) neighbors. If among these deg(u) neighbors, k neighbors are in B^i/2j (x) then u can be at distance [i/2] from only k/deg(u) vertices in Xi. Hence d(Xi) <1/(|BLi/2j(x)| + E N(u)nB'k/2'(x)| uedB rfc/2] (x) deg(u) -). Moreover u andaneighbor v of u in ^/^(x) cannot be both at distance [i/2] from more 326 Ars Math. Contemp. 9 (2015) 165-186 than 2 vertices in X^ therefore uv can only belong to two spheres of radius [¿/2] centered at a vertex in Xj. Hence it follows that d(Xj) < 1 /A(i). □ Corollary 2.3. Let G be a vertex-transitive graph with finite degree, and i be a positive integer. If G has a finite S-packing chromatic number, then œ i § AS) > 1 Corollary 2.4. Let G be a vertex-transitive graph with finite degree, and i be a positive integer. If G has a finite (d, n) -packing chromatic number, then œ En Ai) >1 i=d v ' An i-packing Xi is called a maximized i-packing if for any other i-packing Xi, d(Xi ) > d(Xj ). 2.2 Density of an i-packing in the hexagonal lattice Proposition 2.5. Let H be the hexagonal lattice, x be a vertex in V(h) and n be a positive integer. Then 1. |dBn(x)| = 3n; 2. |Bn(x)| = 3n2 + 3n + 1. Proof. 1. As the set dBn(x) always contains three more vertices than dBn_i(x), then |dBn(x)| = 3n. 2. The graph h is 3-regular and so |B1 (x) | = 4. Suppose the statement is true for n, then |Bn+i(x)| = |Bn(x)| + |dBn+i(x)| = 3 n2 + 3 n + 1 + 3(n + 1) = ( 2 n2 + 3 + 3n) + ( 3n + 3 ) + 1 = 3 (n + 1)2 + 3 (n + 1) + 1 and the result follows by induction. □ Proposition 2.6. Let H be the hexagonal lattice and k be a positive integer. Then 1. A(2k) = 3k2 + 2k + 1; 2. A(4k + 1) = 6k2 + 6k + 2; 3. A(4k + 3) = 6k2 + 12k + 6. Proof. 1. The first property results easily from Proposition 2.5. 2. If n = 4k +1, then Proposition 2.5 gives |B2k(x)| = 2(2k)2 + 2(2k) + 1 = 6k2 + 3k +1. For every vertex y in dB2fc+1(x), y has no neighbor in dB2fc+1(x) other than itself, so |N(y) n dB2fc+1(x)| = 0. We have to distinguish two kinds of vertices: 3k vertices have two neighbors in B2k(x) and |dB2fc+1(x)| - 3k = 3k + 3 vertices have one neighbor in B2k(x). Therefore, |A(4k + 1)| = 6k2 + 3k + 1 + 6k + 3k+3 = 6k2 + 6k + 2. 3. If n = 4k + 3, then Proposition 2.5 gives |B2fc+1(x)| = 3(2k + 1)2 + 3(2k + 1) + 1 = 6k2 + 9k+4. For every vertex y in dB2k+2(x), y has no neighbor in dB2k+2(x)) other than itself, so |N (y)ndB2fc+2 (x) | = 0. We have to distinguish two kinds of vertices: 3k vertices have two neighbors in B2fc+2 (x) and |dB2fc+2 (x) |—3k = 3k+6 vertices have one neighbor in B2k(x). Hence, we have |A(4k + 3)| = 6k2 +9k + 4+ f- + 3k+6 = 6k2 + 12k + 6. □ Note that this result appeared in the article of Goddard and Xu [8]. N. Gastineau andH. Kheddouci: Subdivision into i-packings and S-packing chromatic number... 327 2.3 Density of an i-packing in the square lattice Proposition 2.7. Let Z2 be the square lattice, x be a vertex in V(Z2) and n be a positive integer. Then 1. |dB„(x)| = 4n; 2. |Bn(x)| = 2n2 +2n + 1. Proof. 1. As the set dBn(x) always contains four more vertices than dBn-1(x), then |dB„(x)| =4n. 2. The graph Z2 is 4-regular and so |B1 (x) | = 5. Suppose the statement is true for n, then |Bn+i(x)| = |Bn(x)| + |dBn+i(x)| = 2n2+2n+1+4n+4 = 2(n+1)2+6n+5-4n-2 = 2(n + 1)2 + 2(n + 1) + 1 and the result follows by induction. □ Proposition 2.8. Let Z2 be the square lattice and k be a positive integer. Then 1. A(2k) = 2k2 + 2k + 1; 2. A(2k + 1) = 2k2 +4k + 2. Proof. 1. The first property results easily from Proposition 2.7. 2. If n = 2k + 1, then Proposition 2.7 gives |Bk(x)| = k2 + 2k +1. For every vertex y in dBk+1(x), y has no neighbor in dBk+1(x) other than itself, so |N(y) n dBk+1 (x)| = 0. We have to distinguish two kinds of vertices: 4k vertices have two neighbors in Bk (x) and 4 vertices have one neighbor in Bk(x). Hence, we have |A(2k + 1)| = 2k2 + 2k + 1 + 2 4k + 4 = 2k2 +4k + 2. □ Note that this result appeared implicitly in the article of Fiala et al. [4]. 2.4 Density of an i-packing in the triangular lattice Proposition 2.9. Let T be the triangular lattice, x be a vertex in V (t) and n be a positive integer. Then 1. |dBn (x)| =6n; 2. |Bn(x)| = 3n2 +3n + 1. Proof. 1. As the set dBn(x) always contains six more vertices than dBn-1(x), then |dBn(x)| = 6n. 2. The graph t is 6-regular and so |B1(x)| = 7. Suppose the statement is true for n, then |Bn+1(x)| = |B„(x)| + |dB„+1 (x)| = 3n2 +3n+1+6n+6 = 3(n2 + 1)+3n+1 + 6-3 = 3(n2 + 1) + 3(n + 1) + 1 and the result follows by induction. □ Proposition 2.10. Let T be the triangular lattice and k be a positive integer. Then 1. A(2k) = 3k2 + 3k + 1; 2. A(2k + 1) = 3k2 + 6k + 3. 328 Ars Math. Contemp. 9 (2015) 321-344 r^^n n 1 3 1 4 1 3 1 ^ 1_ 1 4 1 3 1 4 3 1 1 Figure 2: The sets X2 (2-packing), X3 (3-packing) and X4 (4-packing) in h. Proof. 1. The first property result easily from Proposition 2.9. 2. If n = 2k + 1, then Proposition 2.9 gives |Bk (x)| = 3k2 +3k + 1. For every vertex y in dBk+1(x), y has two neighbors in dBk+1(x)) other than itself, so |N(y) n dB2k+1(x)| = 2. We have to distinguish two kinds of vertices: 6k vertices have two neighbors in Bk (x) and six vertices have one neighbor in Bk (x). Hence, we have |A(2k + 1)| = 3k2 + 3k + "" " "" " = 3k2 +6k + 3. □ 1 I 6k+6 | o bk | 1 + 6 + 2 6 + 3 Subdivision of an i-packing in H, Z2 and T 3.1 Subdivision of a 2-packing in H Let X2 be the (unique) maximized 2-packing in h represented in Figure 2. Note that d(X2) = 1/A(2) = 1/4 and remark that four 2-packings form a partition of h if we translate X2 three times. The hexagonal lattice can be seen as a subgraph of the square lattice. In fact in Figure 2, h is represented as subgraph of the usual representation of the square lattice. In the square lattice, we can choose one vertex as the origin and all the other vertices can be nominated by a Cartesian coordinate. In every description of h, our origin (0,0) will be a vertex in the packing that we want to describe such that there is no edge between (0,0) and (0,1). In fact we illustrate packings with a figure in this subsection but it will not be the case after; we will use Cartesian coordinates in order to describe a packing. For example, X2 from Figure 2 is the set of vertices: X2 = {(2x + 4y, x)| x G Z, y G Z}. In Appendix A, we recall a proposition about distance in the hexagonal lattice from Jacko and Jendrol [10]. This proposition is useful to verify that a set is an ¿-packing. These verifications are left to the reader in the remaining propositions. Proposition 3.1. Let k > 0 and m > 0 be integers. There exist: 1. k2 (3k — 1)-packings that form a partition of X2; 2. 2k2 (4k — 1)-packings that form a partition of X2; 3. two (3 x 2k — 1)-packings that form a partition of a (4k — 1)-packings from Point 2; 4. m2 (3mk — 1)-packings that form a partition of a (3k — 1) -packing from Point 1; 5. m2 (4mk — 1)-packings that form a partition of a (4k — 1) -packing from Point 2. 2 2 3 3 4 2 2 2 Proof. 1. Let Ak be the (3k — 1)-packing defined by Ak = {(2kx + 4ky, kx) | x G Z, y G Z}. Let F = {(2i + 4j, ¿) |i, j G {0,..., k — 1} be a family of k2 vectors. Make k2 copies N. Gastineau andH. Kheddouci: Subdivision into i-packings and S-packing chromatic number... 329 1 36 1 36 1 3b 3a 3a 3a ; i , 1 1 36 1 3b 3b 3a 3a i , 1 1 36 1 3b 3b ■ 3* 3a -- 3a -- 0 i X IX T5d |5b p^ fsb I ptrVivii ¿VriS | |5e ~ , | | 5e L5'a I I Figure 3: Two 3-packings forming a partition of X2 (on the left) and four 5-packings forming a partition of X2 (on the right). of the set Ak and translate each one by a vector from F to obtain a partition of X2. 2. Let Bk be the (4k - 1)-packing defined by Bk = {(4kx, 2ky)| x G Z, y G Z}. Let F = {(4i + 2a, 2j + a)|i, j G {0,..., k - 1}, a G {0,1}} be a family of 2k2 vectors. Make 2k2 copies of the set Bk and translate each one by a vector from F to obtain a partition of X2. 3. Note that A2k C Bk and if A2k is A2k translated by the vector (0,2k), then A2k U A2k = Bk . 4. Note that Amk C Ak. Let F = {(2mki + 4mkj, mki)|i, j G {0,..., m - 1}} be a family of m2 vectors. Make m2 copies of the set Amk and translate each one by a vector from F to obtain a partition of Ak . 5. Note that Bmk C Bk .Let F = {(4mki, 2mkj)|i, j G {0,..., m - 1}} be a family of m2 vectors. Make m2 copies of the set Bmk and translate each one by a vector from F to obtain a partition of Bk. □ Figure 3 illustrates a partition of X2 from Points 1 and 2 for k = 1. In the remaining of the section, the proofs of decomposition of a set X will be resumed in a table and the proofs of properties similar from those from Points 3, 4 and 5 will be left to the reader. 3.2 Subdivision of a 3-packing in H Let X3 = {(3x + 6y, x) | x G Z, y G Z} be the maximized 3-packing in H from Figure 2. Note that d(X3) = 1/A(3) = 1/6 and that six 3-packings form a partition of H if we translate X3 five times. Proposition 3.2. Let k > 0 and m > 0 be integers. There exist: 1. k2 pi,k -packings, pi,k = (4k - 1), that form a partition of X3; 2. 3k2 p2k -packings, p2,k = (6k - 1), that form a partition of X3; 3. 8k2 p3,k -packings, p3,k = (10k - 1), that form a partition of X3; 4. 24k2 p4,k -packings, p4,k = (18k - 1), that form a partition of X3; 5. m2 pj mk -packings that form a partition of a pj k -packing from Point j, for j G {!,..', 4}; 330 Ars Math. Contemp. 9 (2015) 165-186 6. three (4 x 3k — 1)-packings that form a partition of a (6k — l)-packing from Point 2; 7. two (4 x 4k — 1)-packings that form a partition of a (10k — 1) -packing from Point 3; 8. four 17-packings and six 23-packings that form a partition of every 5-packing from Point 2. Proof. The proof is resumed in Table B.4, this table contains: in which ¿-packing X will be decomposed (Column 1), the number of ¿-packings needed to form a partition of X (Column 2), the description of an ¿-packing with Cartesian coordinates (assuming x and y are integers) (Column 3) and the family of translation vectors (Column 4). We assume that if we do copies of this ¿-packing and we translate each one by one of these vectors. Afterward, we obtain a partition of X in ¿-packings. □ 3.3 Subdivision of a 4-packing in H Let X4 = {(3x + 7y, 2x + y)| x G Z, y G Z} be the 4-packing in h from Figure 2. Note that d(X4) = 1/11 and that 1/A(4) = 1/10. However, we claim that a 4-packing with density 1/10 does not exist. Note that eleven 4-packings form a partition of h if we translate X4 ten times. Proposition 3.3. Let k > 0 and m > 0 be integers. There exist: 1. k2 p1,k-packings, pi,k = (5k — 1), that form a partition of X4; 2. 2k2 p2,k -packings, p2,k = (6k — 1), that form a partition of X4; 3. 3k2 p3,k -packings, p3,k = (8k — 1), that form a partition of X4; 4. 6k2 p4,k -packings, p4,k = (11k — 1), that form a partition of X4; 5. m2 pj mk -packings that form a partition of a pj k -packing from Point j, for j G {1,..:, 4}; 6. two (5 x 2k — 1)-packings that form a partition of a (6k — 1) -packing from Point 2; 7. two (6k — 1)-packings that form a partition of a (5k — 1)-packing from Point 1; 8. three (5 x 3k — 1)-packings that form a partition of a (8k — 1)-packing from Point 2; 9. three (8k — 1)-packings that form a partition of a (5k — 1)-packing from Point 1. Proof. See Table B.5. □ 3.4 Subdivision of a 2-packing in Z2 In the square lattice, we can choose one vertex as the origin and all the other vertices will be nominated by Cartesian coordinates. In all our representations our origin (0,0) will be in the packing that we want to describe. Let X2 = {(2x + y, x + 3y)| x G Z, y G Z} be the maximized 2-packing in Z2 from Figure 4. Note that d(X2) = 1/A(2) = 1/5 and that five 2-packings form a partition of Z2 if we translate X2 four times. N. Gastineau andH. Kheddouci: Subdivision into i-packings and S-packing chromatic number... 331 - •2 o 2 CH L 3 - -n C> L 3 - -J -0- - - •4 Figure 4: The sets X2 (2-packing), X3 (3-packing) and X4 (4-packing) in Z2. 3 2 3 4 Proposition 3.4. Let k > 0, m > 0 be integers. There exist: 1. k2 (3k — l)-packings that form a partition of X2; 2. 2k2 (4k — l)-packings that form a partition of X2; 3. two (3 x 2k — l)-packings that form a partition of a (4k — 1)-packing from Point 2; 4. two (4k — l)-packings that form a partition of a (3k — 1)-packing from Point 1; 5. m2 (3mk — l)-packings that form a partition of a (3k — 1) -packing from Point 1; 6. m2 (4mk — 1)-packings that form a partition of a (4k — 1) -packing from Point 2. Proof. See Table B.6. □ 3.5 Subdivision of a 3-packing in Z2 Let X3 = {(2x + 4y, 2y)| x G Z, y G Z} be the maximized 3-packing in Z2 from Figure 4. Note that d(X3) = 1/A(3) = 1/8 and that eight 3-packings form a partition of Z2 if we translate X3 seven times. Proposition 3.5. Let k > 0 and m > 0 be integers. There exist: 1. k2 (4k — 1)-packings that form a partition of X3; 2. m2 (4mk — 1)-packings that form a partition of a (4k — 1) -packing from Point 1. Proof. See Table B.6. □ 3.6 Subdivision of a 4-packing in Z2 Let X4 = {(3x + 8y, 2x + y)| x G Z, y G Z} be the maximized 4-packing in Z2 from Figure 4. Note that d(X4) = 1/A(4) = 1/13 and that thirteen 4-packings form a partition of Z2 if we translate X4 twelve times. Proposition 3.6. Let k > 0, m > 0 be integers. There exist: 1. k2 (5k — 1)-packings that form a partition of X4; 2. 2k2 (6k — 1)-packings that form a partition of X4; 3. two (5 x 2k — 1)-packings that form a partition of a (6k — 1)-packing from Point 2; 332 Ars Math. Contemp. 9 (2015) 321-344 \ \ \ \ \ 2 \ \ \ \ \ \ \ \ > \ \ \ \ \ \ \ 2 l_ 3 Figure 5: The sets X1 (1-packing), X2 (2-packing) and X3 (3-packing) in t. 4. two (6k — 1)-packings that form a partition of a (5k — l)-packing from Point 1; 5. m2 (5mk — 1)-packings that form a partition of a (5k — 1) -packing from Point 1; 6. m2 (6mk — 1)-packings that form a partition of a (6k — 1) -packing from Point 2. Proof. See Table B.6. □ 3.7 Subdivision of an independent set in T The square lattice can be seen as a subgraph of the triangular lattice. In fact in Figure 5, the triangular lattice is represented as a supergraph of the square lattice. Therefore, we can choose one vertex as the origin and all the other vertices will be nominated by Cartesian coordinates. In all our representations our origin (0,0) will be a vertex such that (0,0) has (1,0), (0,1), ( —1,0), (0, —1), ( —1,1) and (1, —1) as neighbors. Let Xi = {(x + 3y, x) | x G Z, y G Z} be the (unique) maximized independent set (1-packing) in t from Figure 5. Note that d(X1) = 1/A(1) = 1/3 and that three independent sets form a partition of t if we translate X1 two times. Proposition 3.7. Let k > 0 and m > 0 be integers. There exist: 1. k2 (2k — 1)-packings that form a partition of X1; 2. 3k2 (3k — 1)-packings that form a partition of X1; 3. three (3k — 1)-packings that form a partition of a (2k — 1)-packing from Point 1; 4. m2 (2mk — 1)-packings that form a partition of a (2k — 1) -packing from Point 1; 5. m2 (3mk — 1)-packings that form a partition of a (3k — 1) -packing from Point 2. Proof. See Table B.7. □ 3.8 Subdivision of a 2-packing in T Let X2 = {(2x — y, x + 3y) | x G Z, y G Z} be the maximized 2-packing in t from Figure 5. Note that d(X2) = 1/A(2) = 1/7 and that seven 2-packings form a partition of t if we translate X2 six times. Proposition 3.8. Let k > 0 and m > 0 be integers. There exist: 1. k2 (3k — 1)-packings that form a partition of X2; 2. m2 (3mk — 1)-packings that form a partition of a (3k — 1) -packing from Point 1. Proof. See Table B.7. □ 3 N. Gastineau andH. Kheddouci: Subdivision into i-packings and S-packing chromatic number... 333 3.9 Subdivision of a 3-packing in T Let X3 = {(2x + 6y, 2x)| x G Z, y G Z} be the maximized 3-packing in t from Figure 5. Note that d(X3) = 1 /A(3) = 1/12 and that twelve 3-packings form a partition of t if we translate X3 eleven times. Proposition 3.9. Let k > 0 and m > 0 be integers. There exist: 1. k2 (4k — 1)-packings that form a partition of X3; 2. 3k2 (6k — 1)-packings that form a partition of X3; 3. three (4 x 3k — 1)-packings that form a partition of a (6k — 1) -packing from Point 1; 4. m2 (4mk — 1)-packings that form a partition of a (4k — 1) -packing from Point 1; 5. m2 (6mk — 1)-packings that form a partition of a (6k — 1) -packing from Point 2. Proof. See Table B.7. □ 4 S-packing chromatic number 4.1 General properties In the previous section, we obtained several properties of subdivision of an ¿-packings in a lattice. This section illustrates general properties obtained on the S-packing chromatic number using only a small part of these properties. For a given sequence S, one can find other colorings of a lattice using properties from the previous section. Corollary 4.1. Let a0 = 1. If s1 = 2 and there exist three integers 1 < a1 < ... < a3 and three integers k1,... ,k3 such that sai < 3ki — 1 and a,i — ai-1 > k2 or sai < 4ki — 1 and ai — ai-i > 2k2 for i G {1,..., 3} then xS (h) < a3. This corollary can be useful to find upper bounds for a given sequence. For example, if S = (2,2,2,2,...), then taking a1 = 2, a2 = 3 and a3 = 4, Corollary 4.1 gives us xS(h) < 4 (this result is in fact treated in next subsection). Similarly, for the sequence 5 = (2, 3, 3, 5, 5, 5, 5, 7, 7, 7, 7, 7, 7, 7, 7,...) , then taking a1 = 3, a2 =7 and a3 = 15, Corollary 4.1 gives us x'S (h) < 15. There are similar results for s1 = 3 or s1 =4 using Propositions 3.3 and 3.4. For the two remaining lattices, the two following properties are given for Z2 with s1 =2 and for t with s1 = 1. There exist similar properties for Z2 with s1 = 3 or 4 using Propositions 3.5 and 3.6 and for t with s1 = 2 or 3 using Propositions 3.8 and 3.9. Corollary 4.2. Let a0 = 1. If s1 = 2 and there exist four integers 1 < a1 < ... < a4 and four integers k1,... ,k4 such that sai < 3ki — 1 and ai — ai-1 > k2 or sai < 4ki — 1 and ai — ai-1 > 2k2 for i G {1,..., 4} then xS(Z2) < a4. Corollary 4.3. Let a0 = 1. If s1 = 1 and there exist two integers 1 < a1 < a2 and two integers k1 and k2 such that sai < 2ki — 1 and ai — ai-1 > k2 or sai < 3ki — 1 and ai — ai-1 > 3k2 for i G {1,..., 2} then xS(t) < a2. 334 Ars Math. Contemp. 9 (2015) 165-186 4.2 S-packing chromatic number and distance coloring Jacko and Jendrol [10], Fertin et al. [2] and Sevcikovi [14] have studied distance colorings of h, Z2 and t respectively. The following propositions comes from their work and can be translated in S-packing coloring: Proposition 4.4 ([10]). Let n and d be integers. The minimum n such that s1 = d, sn = d and xS (H) = n is given by \3(d +1)21 for d odd; \§(d + 4/3)2] for d even. Proposition 4.5 ([2]). Let n and d be integers. The minimum n such that s1 = d, sn = d and xS (Z2 ) = n is given by ifj i n2 , 2 (d + 1)2 for d odd; n =i 2 ((d +1)2 + 1) for d even. Proposition 4.6 ([14]). Let n and d be integers. The minimum n such that s1 = d, sn = d and xS (T) = n is given by n= 4(d +1)2 5 (d, n)-packing chromatic number 5.1 Hexagonal lattice Proposition 5.1. ^(h) = rc, x5/(h) = rc, xp'3(h) = rc, ^(h) = rc, XP3'5 (h)= rc and xl6'6(H) = rc. Proof. Let h be the hexagonal lattice and k be an integer, k > 16. k ^ n ^ n ^ k ^ k ^ k ^ E ATI) = E A(2i) + E A(4i+1) + E A(4i+3) = E 3¿2+3¿+1 + E 6i2 + 6i+2 + ¿=1 ¿=1 ¿=0 ¿=0 ¿=1 2 2 ¿=0 k E 6i2+2i+6 < 125tanh(6^^15) + 1 tanh(6+ 36n2 - 1 < 1.494. ¿=0 + + Therefore: t Am < 1.494 - Aft < °."4 < 1 E A2) < 2(1.494 - E Aft) < i=2 i=5 i=1 k 7 k 10 0.955 < 1 E A3) < 3(1.494-E A1)) < °.935 < 1, E a4) < 4(1.494-E A1)) < ¿=8 ¿=1 ¿=11 ¿=1 k 12 k 0.925 < 1 and E Aft < 5(1.494 - E Aft) < 0.986 < 1, E Aft < 6(1.494 - i=13 i=1 i=16 15 E Aft) < 0.968 < 1. Corollary 2.3 allows us to conclude. □ i=1 Proposition 5.2. xp'2(h) < 8, xp'3(h) < 5 and Vn > 4, xp'n(h) = 4. Proof. Using Proposition 3.1, we define a (2, n)-packing coloring of h for each n = 2,3 and n > 4. h can be partitioned into four 2-packings, the first two ones can be colored by color 2, the third one by two colors 3 and the last one by four colors under 5, it will be two 4 and two 5, to conclude xp'2(h) < 8. h can be partitioned into four 2-packings, the N. Gastineau andH. Kheddouci: Subdivision into i-packings and S-packing chromatic number... 335 first three ones can be colored by colors 2 and the third one by two colors 3, to conclude Xp'3 (h) < 5. h can be partitioned into four 2-packings, hence Vn > 4, xp'n (h) =4. □ The following table summarizes the colorings defined in the above proof. The symbol P in the table refers to the packings we use and how we subdivide them into ¿-packings (A is an ¿-packing) and the symbol C refers to the associated colors we use for each ¿-packing. By k x A we mean we use k ¿-packings, and by k x i we mean we use k colors ¿. In the rest of the paper, similar proofs will be only described by a table using the same format than this one. (2,2)-packing P 2xx2 X2 X2 2xa3 4xa5 C 2x2 2x3 2x4,2x5 (2,3)-packing P 3xx2 X2 2xa3 C 3x2 2x3 Proposition 5.3. xp'2(h) < 35, xp'3(h) < 13, xp'4(h) < 10, xp'5(h) < 8 and Vn > 6, xp'n(h) = 6. Proof. Using Proposition 3.2, we define a (3, n)-packing coloring of h for each n = 2.3.4.5 and n > 6. h can be partitioned into six 3-packings, hence Vn > 6, xp'n (h) = 6. The other colorings are described in Table C.8. □ Proposition 5.4. xp'3(h) < 58, xp'4(h) < 27, xp'5(h) < 21, xp'6(h) < 18 and from [10] Vn > 11, xp'n(h) = 11. Proof. Using Proposition 3.3, we define a (4, n)-packing coloring of h for each n = 3.4.5.6 and n > 11. h can be partitioned into eleven 4-packings. The other colorings are described in Table C.9. □ 5.2 Square lattice Proposition 5.5. xp'1 (Z2) = to, xp'2(Z2) = to, xp'3(Z2) = to, xp'4(Z2) = to, Xp0'5(Z2) = to and xp2'6(Z2) = to. Proof. Let Z2 be the square lattice and k be an integer, k > 12. S A(i) = S A(2i) + S A(2i+1) = 2 2i2+2i+1 + S 2i2+4i+2 < in tanh( 2n) + i=1 i=1 i=0 i=1 i=0 n2 - 1 < 1.264. Therefore: £ ^ < L264 - A1) < °.764 < 1, è < 2(L264 - è A1) ) < i=2 i=4 i=1 °.877 < 1, Y A3) < 3(L264 - è ) < °.917 < 1, è A4) < 4(1.264 - è ) < i=6 i=1 i=8 i=1 0.938 < 1, £ A|7 < 5(1.264 - £ ) < 0.951 < 1 and £ A|) < 6(1.264 - i=10 i=1 i=12 11 è Â(ïy ) < 0.959 < 1. Corollary 2.3 allows us to conclude. □ i=1 Proposition 5.6. xP'2(Z2) < 20, xP'3(Z2) < 8, xP'4(Z2) < 6 and Vn > 5, xP'n(Z2) = 5. 336 ArsMath. Contemp. 9(2015)321-344 1 2 1 3 1 2 1 10 1 4 1 7 15 16 13 12 13 13 12 14 17 15 1 4 19 13 12 13 16 1 2 1 15 1 5 1 11 1 2 1 6 1 3 1 2 1 3 1 4 1 14 1 5 1 4 1 16 1 2 1 3 1 3 12 13 16 15 17 1 7 1 10 1 2 1 3 1 2 1 2 13 15 14 18 13 14 12 13 12 19 1 3 1 6 1 13 1 7 1 3 1 2 12 13 12 15 14 1 8 15 14 13 12 13 13 1 2 1 11 1 6 1 10 1 4 17 13 12 13 15 1 2 1 17 1 5 1 4 1 2 1 51312131718 1 10 1 4 1 9 1 2 1 3 1 3 1 2 1 3 1 12 1 5 1 4 16 15 12 13 12 1 2 13 17 14 16 13 1 11 1 2 1 3 1 2 1 13 1 3 14 18 15 13 12 9 1 2 1 3 1 2 1 5 1 4 1 14 1 8 1 5 1 4 1 3 1 2 1 3 1 2 1 3 1 2 1 11 1 6 1 10 1 2 1 4 1 7 1 3 1 2 1 3 1 5 1 3 1 2 1 17 1 5 1 4 1 2 1 3 1 5 1 3 1 2 1 3 1 7 1 8 1 2 1 10 1 4 1 13 1 2 1 3 1 2 1 3 1 2 1 3 1 9 1 5 1 4 1 4 1 6 1 5 1 2 1 3 1 2 1 11 1 2 1 3 1 7 1 4 1 6 1 3 1 5 111 1 2 1 3 1 2 1 12 1 5 1 3 1 4 1 8 1 5 1 3 1 2 1 15 1 2 1 3 1 2 1 10 1 4 1 9 1 7 1 5 1 6 1 3 1 2 1 3 1 2 1 3 1 2 1 4 1 7 1 5 1 2 1 4 1 9 1 3 1 2 1 3 1 6 1 3 1 2 1 14 1 5 1 11 1 2 1 3 1 6 1 3 1 2 1 3 1 4 1 15 1 2 1 5 1 4 1 16 1 2 1 3 1 2 1 3 1 2 1 3 1 6 1 5 1 7 1 11 1 7 1 10 1 2 1 3 1 2 1 4 1 2 1 3 1 5 1 4 1 8 1 3 1 5 1 4 1 2 1 3 1 2 1 9 1 5 1 3 1 6 1 12 1 7 1 3 1 2 1 Figure 6: A 24 x 24 pattern [13]. Proof. Using Proposition 3.4, we define a (2, n)-packing coloring of Z2 for each n = 2,3,4 and n > 5. Z2 can be partitioned into five 2-packings, hence Vn > 5, xp'n(Z2) = 5. The other colorings are described in Table C.10. □ Soukal andHolub [13] have proven that xp'x(Z2) < 17, and proposed a 24 x 24 pattern in order to color the square lattice. Their pattern is recalled in Figure 6. Proposition 5.7. xp'3(Z2) < 33. Proof. In the pattern of Figure 6, B denotes the set of vertices colored by i. Note that B2 and B3 are both 3-packings. It can be seen that B16 U B17 form a 11-packing and that four 7-packings form a partition of B2 or B3. In order to color Z2 starting with 3, we partition 17 B1 into sixteen i-packings, 2 < i < 17 (since B1 is |J Bj translated by the vector (1,0)). i=2 Let Bj denote a copy of Bj translated by (1,0). We use two colors 3 to color B2 and B3, and one color i in order to color Bj for i G [4,8]. We color Bj by one color i, for i G [3, 8] and B2 that is a 3-packing is colored by one color 4, one color 5, one color 6 and one color 7. We use the remaining color 8 to color B9. We use two colors 9 in order to color Bi6, Bj6, B17 and B'7. The remaining color 9 is used to color B'g. We use two colors i in order to color Bj and Bj for i G [10,13]. The remaining colors 10, 11 ,12 and 13 are used to color B14, B'4, B15 and B'5. □ N. Gastineau andH. Kheddouci: Subdivision into i-packings and S-packing chromatic number... 337 Proposition 5.8. x3'4(Z2) < 20, xp'5(Z2) < 17, xp'6(Z2) < 14 andVn > 8, xp'n(Z2) = 8. Proof. Using Proposition 3.5, we define a (3, n)-packing coloring of Z2 for each n = 4,5,6 and n > 8. Z2 can be partitioned into eight 3-packings, hence Vn > 8, xp'n(Z2) = 8. The other colorings are described in Table C.11. □ Proposition 5.9. xp'4(Z2) < 56, xp'5(Z2) < 34, xp'6 (Z2) < 28 and Vn > 13, xp'n(Z2) = 13. Proof. Using Proposition 3.6, we define a (4, n)-packing coloring of Z2 for each n = 4,5,6 and n > 13. Z2 can be partitioned into thirteen 4-packings, hence Vn > 13 Xp'n(Z2) = 13. The other colorings are described in Table C.12. □ 5.3 Triangular lattice Proposition 5.10. xp'Ht = to, x3'2(t) = to, xp'3(t) = to, xp'4(t) = to, xp'5(t) = to andxp'6(t) = to. Proof. Let t be the triangular lattice and k be an integer, k > 8. k k k k k A(i) = ^ A(2i) + 2 A(2i+1) = S 3i2+3i+1 + 2 3i2 + 6i+3 < 3 1 ¿=1 ¿=0 < 3%/3n tanh( 6n\/3) + ¿=1 ¿=1 ¿=0 n2 - 1 < 0.854. Therefore: £ Atf) < 0.854 < 1, £ Ab < 2(0.854 - £ ^ ) < 0.755 < 1, ¿4) < ¿=1 ¿=3 ¿=1 ¿=4 3 k 4 k 3(0.854 - £ Aï)) < 0.883 < 1, £ < 4(0.854 - £ ) < 0.966 < 1, £ ^ < ¿=1 ¿=5 ¿=1 ¿=7 5(0.854 - £ ^) < 0.887 < 1 and £ ^ < 6(0.854 - £ ^) < 0.940 < 1. ¿=1 ¿=8 ¿=1 Corollary 2.3 allows us to conclude. □ Proposition 5.11. xp'2 (t) < 6 and Vn > 3, xp'n(t) = 3. Proof. Using Proposition 3.7, we define a (1, n)-packing coloring of t for each n = 2 and n > 3. t can be partitioned into three independent sets, hence Vn > 3, xp'n(t) = 3. The other coloring is described in the following table. (1,2)-packing P 2xX1 X1 4xA3 C 2x1 2x2, 2x3 □ Proposition 5.12. xp'4(t) < 16, xp'5(t) < 13, xp'6(t) < 10 and Vn > 7, xp'n(t) = 7. Proof. Using Proposition 3.8, we define a (2, n)-packing coloring of t for each n = 4, 5,6 and n > 7. t can be partitioned into seven 2-packings, hence Vn > 7, xp'n(t) = 7. The other colorings are described in Table C.13. □ Proposition 5.13. x3'4(t) < 72, x;3'5(t) < 38, xp'6(t) < 26 and Vn > 12, x3'n(t) = 12. 338 Ars Math. Contemp. 9 (2015) 165-186 Proof. Using Proposition 3.9, we define a (3, n)-packing coloring of t for each n = 4,5,6 and n > 12. t can be partitioned into twelve 3-packings, hence Vn > 12, x3'n(t) = 12. The other colorings are described in Table C.14. □ 6 Conclusion We have determined or bounded the (d, n)-packing chromatic number of three lattices h, Z2 and t for small values of d and n. Further studies can be done with other values of d and n or improving existing values. The (d, n)-packing chromatic number can also be investigated for other lattices. As an example, we can prove, using color patterns defined in [15] for distance graphs, that for the octagonal lattice o, i.e the strong product of two infinite path (which is a supergraph of t), xp'2(®) < 58. For other finite or infinite graphs, like k-regular infinite trees, the method has to be adapted or changed since a maximized packing cannot be described as easily as those considered in this paper. Also, for each of three lattices studied, finding a sequence S such that xS = k and there is no S-packing k coloring where the s1-packing is maximized could be an interesting result. References [1] J. Ekstein, J. Fiala, P. Holub and B. Lidick^, The packing chromatic number of the square lattice is at least 12, arXiv:1003.2291v1 (2010). [2] G. Fertin, E. Godard and A. Raspaud, Acyclic and k-distance coloring of the grid, Information Processing Letters 87 (2003), 51-58. [3] J. Fiala and P. A. Golovach, Complexity of the packing coloring problem for trees, Discrete Applied Mathematics 158 (2010), 771-778. [4] J. Fiala, S. Klavzar and B. Lidick^, The packing chromatic number of infinite product graphs, Europan Journal of Combinatorics 30 (2009), 1101-1113. [5] A. S. Finbow and D. F. Rall, On the packing chromatic number of some lattices, Discrete Applied Mathematics 158 (2010), 1224-1228. [6] N. Gastineau, On dichotomies among the instance of the S-coloring problem, Discrete Mathematics 338 (2015), 1029-1041. [7] W. Goddard, S. M. Hedetniemi, S. T. Hedetniemi, J. M. Harris and D. F. Rall, Broadcast Chromatic Numbers of Graphs, Ars Combinatoria 86 (2008), 33-49. [8] W. Goddard and H. Xu, A note on S-packing colorings of lattices, Discrete Applied Mathematics 166 (2014), 255-262. [9] W. Goddard, H. Xu, The S-packing chromatic number of a graph, Discussiones Mathematicae Graph Theory 32 (2012), 795-806. [10] P. Jacko and S. Jendrol, Distance Coloring of the Hexagonal Lattice, Discussiones Mathematicae Graph Theory 25 (2005), 151-166. [11] D. Korze and A. Vesel, On the packing chromatic number of square and hexagonal lattice, Ars Mathematica Contemporanea 7 (2014), 13-22. [12] F. Kramer and H. Kramer, A survey on the distance-colouring of graphs, Discrete Mathematics 308 (2008), 422-426. [13] R. Soukal and P. Holub, A Note on Packing Chromatic Number of the Square Lattice, The Electronic Journal of Combinatorics 17 (2010), 447-468. [14] A. Sevciková, Distant chromatic number of the planar graphs, Manuscript (2001). N. Gastineau andH. Kheddouci: Subdivision into i-packings and S-packing chromatic number... 339 [15] O. Togni, On packing Colorings of Distance Graphs, Discrete Applied Mathematics 167 (2014), 280-289. A Distances in the three lattices Definition A.1 ([10]). Let v = (a, b) be a vertex in the hexagonal lattice. Then the type of v is t(v) = a + b +1 (mod 2). As h = V0 U Vi is a bipartite graph, the type of a vertex v corresponds to the index of the set V to which v belongs. Proposition A.2 ([10]). Let v1 = (a1, b1), v2 = (a2, b2) be two vertices of the hexagonal lattice and assume that b1 > b2. Then the distance between v1 and v2 is d(v v ) f |ai - a21 + |bi - b2 1 if |a1 - a2 1 > |bi - b2|; d(vi,v2) = j 2|bi - b2|- t(vi)+ t(v2) if |ai - a2| < |bi - b21. Example A.3. The set X2 from Figure 2 is a 2-packing in h. Proof. Let x and y be integers, then d((2(x + 1) + 4y, x + 1), (2x + 4y,x)) = |2x + 4y + 2 - 2x - 4y| + |x + 1 - x| = 3 > 2 and d((2x + 4(y + 1), x), (2x + 4y, x)) = 4 > 2; let i and j be integers, then d((2(x + i) + 4(y + j), x + i), (2x + 4y, x)) > min(d((2(x + 1) + 4y,x + 1), (2x + 4y, x)),d((2x + 4(y + 1),x), (2x + 4y,x))) = 3, hence X2 is a 2-packing. □ Claim A.4. Let v1 = (a1, b1) and v2 = (a2, b2) be two vertices of the square lattice. Then the distance between vi and v2 is d(vi, v2) = |ai - a21 + |bi - 621. Example A.5. The set X2 from Figure 4 is a 2-packing in Z2. Proof. Let x and y be integers, then d((2(x+1)+y,x+1+3y), (2x+y, x+3y)) = |2x+y+2-2x-y| + |x+1+3y-x-3y| = 3 > 2 and d((2x + y + 1, x - 1 + 3(y + 1), (2x + y, x + 3y)) =4 > 2, to conclude X2 is a 2-packing. □ Claim A.6. Let v1 = (a1, b1) and v2 = (a2, b2) be two vertices of the triangular lattice. Then the distance between vi and v2 is d( )=/ max(|ai - a2|, |bi - b21) if ((a1>a2)A(b1b2)); (vi,v2) \ |a1 - a2| + |b1 - b2| otherwise. Example A.7. The set X1 from Figure 5 is an independent set in t. Proof. Let x and y be integers, then, d((x + 1 + 3y, x + 1), (x + 3y, x)) = |x + 1 + 3y - x - 3y| + |x + 1 - x| = 2 > 1 and d((x + 3(y + 1), x), (x + 3y, x)) = 3 > 1, to conclude X1 is an independent set. □ 340 Ars Math. Contemp. 9 (2015) 165-186 B Decomposition of an i-packing in the three lattices i Number of ¿-packings Description of a ¿-packing Family of translation vectors 4k - 1 k2 {3kx + 6ky, kx)} (3i + 6j, i) i,j €{0,...,k-1} 6k - 1 3k2 {3kx + 6ky, 3kx)} (3i + 6j, 3i + 2a) i,j € {0,. .., k - 1}, a € {0, 1, 2} 10k - 1 8k2 {6kx +12ky,4kx)} (6i + 12j + 3b, 4i + 2a + b) i,j €{0,...,k - 1}, a € {0,1, 2, 3}, b € {0, 1} 18k - 1 24k2 {12kx + 24ky, 6kx)} (12i + 24j + 3b, 6i + 2a + b) i,j €{0,...,k - 1}, a € {0, ..., 5}, b € {0,1, 2, 3} Table B.4: Decomposition of in h into ¿-packings. i Number of ¿-packings Description of a ¿-packing Family of translation vectors 5k - 1 k2 {3kx - ky, 2kx + 3ky)} (3i - j, 2i + 3j) ¿,j €{0,...,k - 1} 6k - 1 2k2 {7kx - ky, kx + 3ky)} (7i + 3a - j, i + 2a + 3j) i,j € {0,. .., k - 1}, a € {0,1} 8k - 1 3k2 {7kx + 2ky, kx + 5ky)} (7i + 2j + 3a, i + 5j + 2a) i,j € {0, ..., k - 1}, a € {0, 1, 2} 11k - 1 6k2 {-2kx + 11ky, 6kx)} (-2i + 11j + 7a, 6i + a) i, j € {0,. .., k - 1}, a € {0, ..., 5} Table B.5: Decomposition of X4 in h into ¿-packings. N. Gastineau andH. Kheddouci: Subdivision into i-packings and S-packing chromatic number... 341 i Number of ¿-packings Description of a ¿-packing Family of translation vectors X2 3k - 1 k2 {2kx - ky, kx + 2ky)} (2i - + 2 j) ¿j e{o,...,k-1} 4k - 1 2 1: {4kx + ky, 2kx + 3ky)} (4i + 2a + j, 2¿ + 2a + 3j) ¿,j € {0, ...,k - 1}, a € {0,1} X3 4k - 1 k2 {2kx + 4ky, 2kx)} ^ + 4j, 2¿) ¿,j €{0,...,k - 1} X4 5k - 1 k2 {3kx - 2ky, 2kx + 3ky)} (3¿ - 2j, 2¿ + 3j) ¿,j €{0,...,k - 1} 6k - 1 2 1: {6kx + ky, 4kx + 5ky)} (6¿ + j + 3a, 4¿ + 5j + 2a) ¿,j € {0, ...,k - 1}, a € {0,1} Table B.6: Decomposition of X2, X3 and X4 in Z2 into ¿-packings. ¿ Number of ¿-packings Description of a ¿-packing Family of translation vectors Xi 2k - 1 k2 {kx + 3ky, kx)} ^ + 3j,¿) ¿,j €{0,...,k - 1} 3k - 1 3k2 {3kx + 3ky, 3kx)} (3¿ + 3j + a, 3¿ + a) ¿,j € {0,. .., k - 1}, a € {0, 1, 2} X2 3k - 1 k2 {2kx + 7ky, kx)} ^ + 7j,¿) ¿,j €{0,...,k - 1} X3 4k - 1 k2 {2kx + 6ky, 2kx)} (2¿ + 6j, 2¿) ¿,j €{0,...,k - 1} 6k - 1 3k2 {6kx + 6ky,6kx)} (6¿ + 6j + 2a, 6¿ + 2a) ¿,j € {0,. .., k - 1}, a € {0, 1, 2} Table B.7: Decomposition of Xi, X2 and X3 in t into ¿-packings. 342 Ars Math. Contemp. 9 (2015) 165-186 C Decomposition and associated colors X3 X3 X3 X3 P 2xx3 3xx5 4xx7 4xx9, 8xx15 X5, 3xXii, (3,2)-packing 4xXi7, 6xx23 C 2x3 2x4,5 2x6, 2x7 2x8, 2x9, 2x12,2x13, 2x14, 2x15 5,2x10,2x11, 2x16,2x17,2x18, 2x19, 20 P 3xx3 X3 X3 X3 (3,3)-packing 3xx5 3xx5 4xx7 C 3x3 3x4 3x5 3x6,7 P 4xx3 X3 X3 (3,4)-packing 3xx5 3xx5 C 4x3 3x4 4,2x5 P 5xx3 X3 (3,5)-packing 3xx5 C 5x3 3x4 Table C.8: Decomposition of H into 3-packings and associated colors. N. Gastineau andH. Kheddouci: Subdivision into i-packings and S-packing chromatic number... 343 (4,3)-packing P 3xX4 X4 2xX4 2xX4 X4 2xA5 6xA7 A5, 6xAQ 6xA11,4xA19 C 3x4 2x5 3x6, 3x7 5, 3x8, 3x9 3x10, 3x11, 18, 3x19 P X4 X4 9xAi4 11xA19, 10x A23 C 3x12, 3x13, 3x14 3x15, 3x16, 3x17, 2x18, 3x20, 3x21 3x22, 23 (4,4)-packing P 4xX4 2xX4 2xX4 2xX4 X4 4x A5 6xA7 8xA9 2xA7, 3xA14 C 4x4 4x5 4x6, 2x7 4x8,4x9 2x7, 3x10 (4,5)-packing P 5xX4 2xX4 3xX4 X4 4x A5 9xA7 A5,2xA9 C 5x4 4x5 5x6,4x7 5, 7,8 (4,6)-packing P 6xX4 3xX4 2xX4 6XA5 6xA7 C 6x4 6x5 6x6 Table C.9: Decomposition of h into 4-packings and associated colors. (2,2)-packing P 2xx2 x2 x2 x2 2xa3 4x a5 6xa8, 6xa11 C 2x2 2x3 2x4,2x5 2x6,2x7,2x8 2x9,2x10,2x11 (2,3)-packing P 3xx2 x2 x2 2xa3 a3,2xa5 C 3x2 2x3 3,2x4 (2,4)-packing P 4xx2 X2 2xa3 C 4x2 2x3 Table C.10: Decomposition of Z2 into 2-packings and associated colors. (3,4)-packing P 4xx3 4xx3 16xa7 C 4x3 4x4, 4x5, 4x6, 4x7 (3,5)-packing P 5xx3 3xx3 12xa7 C 5x3 5x4, 5x5, 2x6 (3,6)-packing P 6XX3 2xX3 8xA7 C 6x3 6x4,2x5 Table C.11: Decomposition of Z2 into 3-packings and associated colors. 344 Ars Math. Contemp. 9 (2015) 165-186 P 4xX4 2xX4 4xX4 X4 X4 X4 (4,4)-packing 4xA5 16x A9 8xA11 9xA14 3xA14, 12xA17 C 4x4 4x5 4x6, 4x7, 4x10, 4x12 3x14,4x15, 4x8,4x9 4x11 4x13, 14 4x16,4x17 5xX4 2xX4 5xX4 X4 P 4xA5 A5, 18xA9 2xA9, (4,5)-packing 4xA11 C 5x4 4x5 5, 5x6, 5x7 2x9, 5x8, 3x9 4x10 P 6xX4 3xX4 4xX4 (4,6)-packing 6xA5 16x A9 C 6x4 6x5 6x6,6x7,4x8 Table C.12: Decomposition of Z2 into 4-packings and associated colors. (2,4)-packing P 4xX2 3xX2 12xA5 C 4x2 4x3,4x4,4x5 (2,5)-packing P 5xX2 2xX2 8x A5 C 5x2 5x3, 3x4 (2,6)-packing P 6xX2 X2 4x A5 C 6x2 4x3 Table C.13: Decomposition of t into 2-packings and associated colors. (3,4)-packing P 4xX3 2xX3 2xX3 2xX3 6xA5 8xAr 2xA5, 12xA11 C 4x3 4x4,2x5 4x6, 4x7 2x5,4x9,4x10,4x11 P X3 X3 16xA15 4xAn,20xA23 C 4x12,4x13 4x14,4x15 4x8,4x16,4x17, 4x18,4x19,4x20 (3,5)-packing P 5xX3 3xX3 2xX3 2xX3 9xA5 8xAr 18x A11 C 5x3 5x4,4x5 5x6, 3x7 5, 2x7, 5x8, 5x9, 3x10 (3,6)-packing P 6xX3 4xX3 2xX3 12xA5 8xA7 C 6x3 6x4, 6x5 6x6, 2x7 Table C.14: Decomposition of t into 3-packings and associated colors.