# Subdivision into i-packings and S-packing chromatic number of some lattices

Nicolas Gastineau, Hamamache Kheddouci, Olivier Togni

<figure><img src="image_1.png" /></figure>

To cite this version:

Nicolas Gastineau, Hamamache Kheddouci, Olivier Togni. Subdivision into i-packings and S-packing chromatic number of some lattices. Ars Mathematica Contemporanea, 2015, 9. hal-01157901

HAL Id: hal-01157901

https://u-bourgogne.hal.science/hal-01157901

Submitted on 28 May 2015

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Subdivision into *i*-packings and *S*-packing
chromatic number of some lattices

Nicolas Gastineau*¹,², Hamamache Kheddouci² and Olivier Togni¹

¹Université de Bourgogne, 21078 Dijon cedex, France, Le2i, UMR CNRS 6303

²Université de Lyon, CNRS, Université Lyon 1, LIRIS, UMR5205, F-69622, France

May 28, 2015

Abstract

An *i*-packing in a graph *G* is a set of vertices at pairwise distance greater than *i*. For a nondecreasing sequence of integers *S* = (*s*₁, *s*₂, ...), 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 *s*<sub>*i*</sub>-packing. This paper describes various subdivisions of an *i*-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* = (*s*<sub>*i*</sub>, *i* ∈ N*), *s*<sub>*i*</sub> = *d* + ⌊(*i* − 1)/*n*⌋.

# 1 Introduction

Let $G = (V, E)$ be a (finite or infinite) graph and let $N(u) = \{v \in V(G) | uv \in E(G)\}$ be the set of neighbors of vertex $u$. A set $X_i \subseteq V(G)$ is an $i$-packing if for any distinct pair $u, v \in X_i$, $d(u, v) > i$, where $d(u, v)$ denotes the usual shortest path distance between $u$ and $v$. We will use $X_i$ to refer to an $i$-packing in a graph $G$. A $k$-coloring $c$ of $G$ is a map from $V(G)$ to $\{1, \dots, k\}$ such that for every pair of adjacent vertices $(u, v)$, we have $c(u) \neq c(v)$. For a graph $G$ and a $k$-coloring $c$ of $G$, let $c_i$ be $\{u \in 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 \le i \le k$, $c_i$ is a $i$-packing, is called the *packing chromatic number* of $G$ and is denoted by $\chi_p(G)$. This concept was introduced by Goddard et al. [7] under the name of broadcast chromatic number. More generally, for a nondecreasing sequence

<footnote>*Author partially supported by the Burgundy Council</footnote>
of integers $S = (s_1, s_2, \dots)$, an $S$-packing $k$-coloring is a $k$-coloring $c$ of $V(G)$ such that for every $i$, with $1 \le i \le k$, $c_i$ is a $s_i$-packing. Such a coloring will also simply be called an $(s_1, \dots, s_k)$-coloring. The $S$-packing chromatic number of $G$ denoted by $\chi_{\rho}^{S}(G)$, is the smallest $k$ such that $G$ admits an $S$-packing $k$-coloring. For the sequences $S = (s_i, i \in \mathbb{N}^*)$, with $s_i = d + \lfloor(i-1)/n\rfloor$, we call $\chi_{\rho}^{S}(G)$ the $(d, n)$-packing chromatic number and denote it by $\chi_{\rho}^{d, n}(G)$. For any connected graph $G$ such that $|V(G)| \ge d+1$, $\chi_{\rho}^{d, n}(G) \ge d+1$ and $\chi_{\rho}^{1, 1}(G) = \chi_{\rho}(G)$. For every bipartite graph $G$, $\chi_{\rho}^{1, 2}(G) = 2$ (a bipartite graph is 2-colorable). Moreover, the smallest $n$ such that $\chi_{\rho}^{d, 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 $P_{\infty}$ denote the two-way infinite path, let $\mathbb{Z}^2 = P_{\infty} \square P_{\infty}$ denote the planar square lattice (where $\square$ is the Cartesian product), $\mathcal{T}$ denote the planar triangular lattice and $\mathcal{H}$ denote the planar hexagonal lattice. In this article, for an $(s_1, s_2, \dots)$-coloring of a graph, we prefer to map vertices to the color multiset $\{s_1, s_2, \dots\}$ 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 $i_a, i_b, \dots$.

## 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 [14] proved that $\chi_{\rho}(\mathbb{Z}^2) \le 17$, Ekstein et al. [1] that $12 \le \chi_{\rho}(\mathbb{Z}^2)$; Fiala et al. [4] showed that $\chi_{\rho}(\mathcal{H}) \le 7$, $\chi_{\rho}(\mathbb{Z}^2 \square P_2) = \infty$ and $\chi_{\rho}(\mathcal{H} \square P_6) = \infty$ and Finbow and Rall [5] proved that $\chi_{\rho}(\mathcal{T}) = \infty$.

$S$-packing colorings with sequences $S$ other than $(1, 2, \dots, 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,
<table><caption>Table 1: Bounds for $(d, n)$-packing chromatic numbers of the hexagonal lattice.</caption><thead><tr><th>d \ n</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th></tr></thead><tbody><tr><td>1</td><td>7[11, 4]</td><td>2</td><td>2</td><td>2</td><td>2</td><td>2</td></tr><tr><td>2</td><td>∞</td><td>5 - 8</td><td>5</td><td>4</td><td>4</td><td>4</td></tr><tr><td>3</td><td>∞</td><td>15 - 35</td><td>9 - 13</td><td>8 - 10</td><td>7 - 8</td><td>6</td></tr><tr><td>4</td><td>∞</td><td>61 - ?</td><td>20 - 58</td><td>15 - 27</td><td>13 - 21</td><td>12 - 18</td></tr><tr><td>5</td><td>∞</td><td>∞</td><td>37 - ?</td><td>25 - ?</td><td>21 - ?</td><td>19 - ?</td></tr><tr><td>8</td><td>∞</td><td>∞</td><td>∞</td><td>?</td><td>?</td><td>?</td></tr><tr><td>11</td><td>∞</td><td>∞</td><td>∞</td><td>∞</td><td>?</td><td>?</td></tr><tr><td>13</td><td>∞</td><td>∞</td><td>∞</td><td>∞</td><td>∞</td><td>?</td></tr><tr><td>16</td><td>∞</td><td>∞</td><td>∞</td><td>∞</td><td>∞</td><td>∞</td></tr></tbody></table>

but the parameter $n$ allows us to control its growth.

Moreover, one can note that all the $S$-packing colorings of square and hexagonal lattices published so far have the property that the $s_1$-packing is maximum and the other $s_i$-packings are obtained by subdivisions of $s_1$-packings (and are not always maximum). Therefore, we find it interesting to study subdivision of an $i$-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 is satisfied remains an open question. Recently Goddard and Xu [8] proved that there exist nondecreasing sequences $S$ such that $P_\infty$ is $S$-colorable and in any $(s_1, \dots, \chi_\rho^S(P_\infty))$-packing coloring of $P_\infty$, the $s_1$-packing is not maximum, showing that for $P_\infty$, 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 $\mathcal{H}$, $\mathbb{Z}^2$ and $\mathcal{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].
<table><caption>Table 2: Bounds for $(d, n)$-packing chromatic numbers of the square lattice.</caption><thead><tr><th>d\n</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th></tr></thead><tbody><tr><td>1</td><td>12 - 17 [1, 14]</td><td><b>2</b></td><td><b>2</b></td><td><b>2</b></td><td><b>2</b></td><td><b>2</b></td></tr><tr><td>2</td><td>∞</td><td>11 - 20</td><td>7 - 8</td><td><b>6</b> [8]</td><td><b>5</b> [8]</td><td><b>5</b></td></tr><tr><td>3</td><td>∞</td><td>57 - ?</td><td>16 - 33</td><td>12 - 20</td><td>10 - 17</td><td>10 - 14</td></tr><tr><td>4</td><td>∞</td><td>∞</td><td>44 - ?</td><td>25 - 56</td><td>20 - 34</td><td>18 - 28</td></tr><tr><td>5</td><td>∞</td><td>∞</td><td>199 - ?</td><td>50 - ?</td><td>35 - ?</td><td>29 - ?</td></tr><tr><td>6</td><td>∞</td><td>∞</td><td>∞</td><td>?</td><td>?</td><td>?</td></tr><tr><td>8</td><td>∞</td><td>∞</td><td>∞</td><td>∞</td><td>?</td><td>?</td></tr><tr><td>10</td><td>∞</td><td>∞</td><td>∞</td><td>∞</td><td>∞</td><td>?</td></tr><tr><td>12</td><td>∞</td><td>∞</td><td>∞</td><td>∞</td><td>∞</td><td>∞</td></tr></tbody></table>

<table><caption>Table 3: Bounds for $(d, n)$-packing chromatic numbers of the triangular lattice.</caption><thead><tr><th>d\n</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th></tr></thead><tbody><tr><td>1</td><td>∞[5]</td><td>5 - 6 [8]</td><td><b>3</b></td><td><b>3</b></td><td><b>3</b></td><td><b>3</b></td></tr><tr><td>2</td><td>∞</td><td>127 - ?</td><td>14 - ?</td><td>10 - 16</td><td>9 - 13</td><td>8 - 10</td></tr><tr><td>3</td><td>∞</td><td>∞</td><td>81 - ?</td><td>28 - 72</td><td>20 - 38</td><td>17 - 26</td></tr><tr><td>4</td><td>∞</td><td>∞</td><td>∞</td><td>104 - ?</td><td>49 - ?</td><td>36 - ?</td></tr><tr><td>5</td><td>∞</td><td>∞</td><td>∞</td><td>∞</td><td>?</td><td>?</td></tr><tr><td>7</td><td>∞</td><td>∞</td><td>∞</td><td>∞</td><td>∞</td><td>?</td></tr><tr><td>8</td><td>∞</td><td>∞</td><td>∞</td><td>∞</td><td>∞</td><td>∞</td></tr></tbody></table>
<figure><img src="image_3.png" /><figcaption>Figure 1: Examples of $k$-area in $\mathcal{T}$.</figcaption></figure>

# 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 $B_n(x) = \{v \in V(G) | d_G(x, v) \le n\}$ and the sphere of radius $n$ centered at $x$ is the set $\partial B_n(x) = \{v \in V(G) | d_G(x, v) = n\}$. The density of a set of vertices $X \subseteq V(G)$ is $d(X) = \limsup_{l \to \infty} \max_{x \in V} \{\frac{|X \cap B_l(x)|}{|B_l(x)|}\}$.

The notion of $k$-area was introduced by Fiala et al. [4]. We propose here a slightly modified definition:

**Definition 2.1.** Let $G$ be a graph, $x \in V(G)$, and let $k$ be a positive integer. The $k$-area $A(x, k)$ assigned to $G$ is defined by:

$$A(x, k) = \begin{cases} |B_{k/2}(x)| & \text{for } k \text{ even;} \\ |B_{\lceil k/2 \rceil}(x)| + \sum_{u \in \partial B_{\lceil k/2 \rceil}(x)} \frac{|N(u) \cap B_{\lceil k/2 \rceil}(x)| + |N(u) \cap \partial B_{\lceil k/2 \rceil}(x)|/2}{\deg(u)} & \text{for } k \text{ odd.} \end{cases}$$

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 \in \partial B_1(x)$, $|N(u) \cap \partial B_1(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) \cap \partial B_1(x)|/2 = 1$.
**Proposition 2.2.** Let G be a vertex-transitive graph with finite degree, and i be a positive integer. If $X_i$ is an i-packing in G, then

$$d(X_i) \leq \frac{1}{A(i)}.$$

*Proof.* Observe that for arbitrary vertices $x$ and $y$ of an $i$-packing $X_i$, the sets $B_{\lfloor i/2 \rfloor}(x)$ and $B_{\lfloor i/2 \rfloor}(y)$ are disjoint, since the vertices $x$ and $y$ are at distance greater than $i$. Then $d(X_i) < 1/|B_{\lfloor i/2 \rfloor}(x)|$. Assume that $i$ is an odd number and let $u$ be a vertex at distance $\lfloor i/2 \rfloor$ from $x$, then $u$ has $\deg(u)$ neighbors. If among these $\deg(u)$ neighbors, $k$ neighbors are in $B_{\lfloor i/2 \rfloor}(x)$ then $u$ can be at distance $\lfloor i/2 \rfloor$ from only $k/\deg(u)$ vertices in $X_i$. Hence $d(X_i) < 1/(|B_{\lfloor i/2 \rfloor}(x)|+$

$$\sum_{u \in \partial B_{\lfloor k/2 \rfloor}(x)} \frac{|N(u) \cap B_{\lfloor k/2 \rfloor}(x)|}{\deg(u)}).$$

Moreover $u$ and a neighbor $v$ of $u$ in $B_{\lfloor i/2 \rfloor}(x)$ cannot be both at distance $\lfloor i/2 \rfloor$ from more than 2 vertices in $X_i$, therefore $uv$ can only belong to two spheres of radius $\lfloor i/2 \rfloor$ centered at a vertex in $X_i$. Hence it follows that $d(X_i) < 1/A(i)$. $\square$

**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

$$\sum_{i=1}^{\infty} \frac{1}{A(s_i)} \geq 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

$$\sum_{i=d}^{\infty} \frac{n}{A(i)} \geq 1.$$

An $i$-packing $X_i$ is called a *maximized i-packing* if for any other $i$-packing $X'_i$, $d(X_i) \geq d(X'_i)$.

## 2.2 Density of an i-packing in the hexagonal lattice

**Proposition 2.5.** Let $\mathcal{H}$ be the hexagonal lattice, $x$ be a vertex in $V(\mathcal{H})$ and $n$ be a positive integer. Then

1. $|\partial B_n(x)| = 3n;$

2. $|B_n(x)| = \frac{3}{2}n^2 + \frac{3}{2}n + 1.$

*Proof.* 1. As the set $\partial B_n(x)$ always contains three more vertices than $\partial B_{n-1}(x)$, then $|\partial B_n(x)| = 3n$.

2. The graph $\mathcal{H}$ is 3-regular and so $|B_1(x)| = 4$. Suppose the statement is true for $n$, then $|B_{n+1}(x)| = |B_n(x)| + |\partial B_{n+1}(x)| = \frac{3}{2}n^2 + \frac{3}{2}n + 1 + 3(n+1) = (\frac{3}{2}n^2 + \frac{3}{2} + 3n) + (\frac{3}{2}n + \frac{3}{2}) + 1 = \frac{3}{2}(n+1)^2 + \frac{3}{2}(n+1) + 1$ and the result follows by induction. $\square$
**Proposition 2.6.** Let $\mathcal{H}$ be the hexagonal lattice and $k$ be a positive integer.
Then

1. $A(2k) = \frac{3}{2}k^2 + \frac{3}{2}k + 1;$

2. $A(4k + 1) = 6k^2 + 6k + 2;$

3. $A(4k + 3) = 6k^2 + 12k + 6.$

*Proof.* 1. The first property results easily from Proposition 2.5.

2. If $n = 4k + 1$, then Proposition 2.5 gives $|B_{2k}(x)| = \frac{3}{2}(2k)^2 + \frac{3}{2}(2k) + 1 = 6k^2 + 3k + 1$. For every vertex $y$ in $\partial B_{2k+1}(x)$, $y$ has no neighbor in $\partial B_{2k+1}(x)$ other than itself, so $|N(y) \cap \partial B_{2k+1}(x)| = 0$. We have to distinguish two kinds of vertices: $3k$ vertices have two neighbors in $B_{2k}(x)$ and $|\partial B_{2k+1}(x)| - 3k = 3k + 3$ vertices have one neighbor in $B_{2k}(x)$. Therefore, $|A(4k+1)| = 6k^2 + 3k + 1 + \frac{6k}{3} + \frac{3k+3}{3} = 6k^2 + 6k + 2$.

3. If $n = 4k + 3$, then Proposition 2.5 gives $|B_{2k+1}(x)| = \frac{3}{2}(2k+1)^2 + \frac{3}{2}(2k+1) + 1 = 6k^2 + 9k + 4$. For every vertex $y$ in $\partial B_{2k+2}(x)$, $y$ has no neighbor in $\partial B_{2k+2}(x)$ other than itself, so $|N(y) \cap \partial B_{2k+2}(x)| = 0$. We have to distinguish two kinds of vertices: $3k$ vertices have two neighbors in $B_{2k+2}(x)$ and $|\partial B_{2k+2}(x)| - 3k = 3k + 6$ vertices have one neighbor in $B_{2k}(x)$. Hence, we have $|A(4k+3)| = 6k^2 + 9k + 4 + \frac{6k}{3} + \frac{3k+6}{3} = 6k^2 + 12k + 6$. $\square$

Note that this result appeared in the article of Goddard and Xu [8].

## 2.3 Density of an $i$-packing in the square lattice

**Proposition 2.7.** Let $\mathbb{Z}^2$ be the square lattice, $x$ be a vertex in $V(\mathbb{Z}^2)$ and $n$ be a positive integer. Then

1. $|\partial B_n(x)| = 4n;$

2. $|B_n(x)| = 2n^2 + 2n + 1.$

*Proof.* 1. As the set $\partial B_n(x)$ always contains four more vertices than $\partial B_{n-1}(x)$, then $|\partial B_n(x)| = 4n$.

2. The graph $\mathbb{Z}^2$ is 4-regular and so $|B_1(x)| = 5$. Suppose the statement is true for $n$, then $|B_{n+1}(x)| = |B_n(x)| + |\partial B_{n+1}(x)| = 2n^2 + 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. $\square$

**Proposition 2.8.** Let $\mathbb{Z}^2$ be the square lattice and $k$ be a positive integer. Then

1. $A(2k) = 2k^2 + 2k + 1;$

2. $A(2k + 1) = 2k^2 + 4k + 2.$

*Proof.* 1. The first property results easily from Proposition 2.7.

2. If $n = 2k + 1$, then Proposition 2.7 gives $|B_k(x)| = k^2 + 2k + 1$. For every vertex $y$ in $\partial B_{k+1}(x)$, $y$ has no neighbor in $\partial B_{k+1}(x)$ other than itself, so
$|N(y) \cap \partial B_{k+1}(x)| = 0$. We have to distinguish two kinds of vertices: $4k$ vertices have two neighbors in $B_k(x)$ and $4$ vertices have one neighbor in $B_k(x)$. Hence, we have $|A(2k+1)| = 2k^2 + 2k + 1 + 2\frac{4k}{4} + \frac{4}{4} = 2k^2 + 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 $\mathcal{T}$ be the triangular lattice, $x$ be a vertex in $V(\mathcal{T})$ and $n$ be a positive integer. Then

$$1. \quad |\partial B_n(x)| = 6n;$$

$$2. \quad |B_n(x)| = 3n^2 + 3n + 1.$$

*Proof.* 1. As the set $\partial B_n(x)$ always contains six more vertices than $\partial B_{n-1}(x)$, then $|\partial B_n(x)| = 6n$.

2. The graph $\mathcal{T}$ is 6-regular and so $|B_1(x)| = 7$. Suppose the statement is true for $n$, then $|B_{n+1}(x)| = |B_n(x)| + |\partial B_{n+1}(x)| = 3n^2 + 3n + 1 + 6n + 6 = 3(n^2 + 1) + 3n + 1 + 6 - 3 = 3(n^2 + 1) + 3(n + 1) + 1$ and the result follows by induction. □

**Proposition 2.10.** Let $\mathcal{T}$ be the triangular lattice and $k$ be a positive integer. Then

$$1. \quad A(2k) = 3k^2 + 3k + 1;$$

$$2. \quad A(2k + 1) = 3k^2 + 6k + 3.$$

*Proof.* 1. The first property result easily from Proposition 2.9.

2. If $n = 2k + 1$, then Proposition 2.9 gives $|B_k(x)| = 3k^2 + 3k + 1$. For every vertex $y$ in $\partial B_{k+1}(x)$, $y$ has two neighbors in $\partial B_{k+1}(x)$) other than itself, so $|N(y) \cap \partial B_{2k+1}(x)| = 2$. We have to distinguish two kinds of vertices: $6k$ vertices have two neighbors in $B_k(x)$ and six vertices have one neighbor in $B_k(x)$. Hence, we have $|A(2k+1)| = 3k^2 + 3k + 1 + \frac{6k+6}{6} + 2\frac{6k}{6} + \frac{6}{6} = 3k^2 + 6k + 3$. □

# 3 Subdivision of an i-packing in $\mathcal{H}, \mathbb{Z}^2$ and $\mathcal{T}$

## 3.1 Subdivision of a 2-packing in $\mathcal{H}$

Let $X_2$ be the (unique) maximized 2-packing in $\mathcal{H}$ represented in Figure 2. Note that $d(X_2) = 1/A(2) = 1/4$ and remark that four 2-packings form a partition of $\mathcal{H}$ if we translate $X_2$ three times.

The hexagonal lattice can be seen as a subgraph of the square lattice. In fact in Figure 2, $\mathcal{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 $\mathcal{H}$, our origin $(0, 0)$ will be a vertex in the packing that we want to
<figure><img src="image_4.png" /><figcaption>Figure 2: The sets $X_2$ (2-packing), $X_3$ (3-packing) and $X_4$ (4-packing) in $\mathcal{H}$.</figcaption></figure>

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, $X_2$
from Figure 2 is the set of vertices: $X_2 = \{(2x + 4y, x) | x \in \mathbb{Z}, y \in \mathbb{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 $i$-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. $k^2 (3k - 1)$-packings that form a partition of $X_2$;

2. $2k^2 (4k - 1)$-packings that form a partition of $X_2$;

3. two $(3 \times 2k - 1)$-packings that form a partition of a $(4k - 1)$-packings from Point 2;

4. $m^2 (3mk - 1)$-packings that form a partition of a $(3k - 1)$-packing from Point 1;

5. $m^2 (4mk - 1)$-packings that form a partition of a $(4k - 1)$-packing from Point 2.

*Proof.* 1. Let $A_k$ be the $(3k-1)$-packing defined by $A_k = \{(2kx+4ky,kx)| x \in \mathbb{Z}, y \in \mathbb{Z}\}$. Let $\mathcal{F} = \{(2i+4j,i)|i,j \in \{0,\dots,k-1\}\}$ be a family of $k^2$ vectors. Make $k^2$ copies of the set $A_k$ and translate each one by a vector from $\mathcal{F}$ to obtain a partition of $X_2$.

2. Let $B_k$ be the $(4k-1)$-packing defined by $B_k = \{(4kx, 2ky) | x \in \mathbb{Z}, y \in \mathbb{Z}\}$. Let $\mathcal{F} = \{(4i+2a, 2j+a) | i, j \in \{0, \dots, k-1\}, a \in \{0, 1\}\}$ be a family of $2k^2$ vectors. Make $2k^2$ copies of the set $B_k$ and translate each one by a vector from $\mathcal{F}$ to obtain a partition of $X_2$.

3. Note that $A_{2k} \subseteq B_k$ and if $A'_{2k}$ is $A_{2k}$ translated by the vector $(0, 2k)$, then $A'_{2k} \cup A_{2k} = B_k$.

4. Note that $A_{mk} \subseteq A_k$. Let $\mathcal{F} = \{(2mki + 4mkj, mki) | i, j \in \{0, \dots, m-1\}\}$ be a family of $m^2$ vectors. Make $m^2$ copies of the set $A_{mk}$ and translate each one by a vector from $\mathcal{F}$ to obtain a partition of $A_k$.

5. Note that $B_{mk} \subseteq B_k$. Let $\mathcal{F} = \{(4mki, 2mkj) | i, j \in \{0, \dots, m-1\}\}$ be a
<figure><img src="image_5.png" /><figcaption>Figure 3: Two 3-packings forming a partition of $X_2$ (on the left) and four 5-packings forming a partition of $X_2$ (on the right).</figcaption></figure>

family of $m^2$ vectors. Make $m^2$ copies of the set $B_{mk}$ and translate each one by a vector from $\mathcal{F}$ to obtain a partition of $B_k$. $\square$

Figure 3 illustrates a partition of $X_2$ 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 $\mathcal{H}$

Let $X_3 = \{(3x + 6y, x) | x \in \mathbb{Z}, y \in \mathbb{Z}\}$ be the maximized 3-packing in $\mathcal{H}$ from Figure 2. Note that $d(X_3) = 1/A(3) = 1/6$ and that six 3-packings form a partition of $\mathcal{H}$ if we translate $X_3$ five times.

**Proposition 3.2.** Let $k > 0$ and $m > 0$ be integers. There exist:

1. $k^2 p_{1,k}$-packings, $p_{1,k} = (4k-1)$, that form a partition of $X_3$;

2. $3k^2 p_{2,k}$-packings, $p_{2,k} = (6k-1)$, that form a partition of $X_3$;

3. $8k^2 p_{3,k}$-packings, $p_{3,k} = (10k-1)$, that form a partition of $X_3$;

4. $24k^2 p_{4,k}$-packings, $p_{4,k} = (18k-1)$, that form a partition of $X_3$;

5. $m^2 p_{j,mk}$-packings that form a partition of a $p_{j,k}$-packing from Point $j$, for $j \in \{1, \dots, 4\}$;

6. three $(4 \times 3k-1)$-packings that form a partition of a $(6k-1)$-packing from Point 2;

7. two $(4 \times 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 *i*-packing *X* will be decomposed (Column 1), the number of *i*-packings needed to form a partition of *X* (Column 2), the description of an *i*-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 *i*-packing and we translate each one by one of these vectors. Afterward, we obtain a partition of *X* in *i*-packings.

□

## 3.3 Subdivision of a 4-packing in $\mathcal{H}$

Let $X_4 = \{(3x + 7y, 2x + y) | x \in \mathbb{Z}, y \in \mathbb{Z}\}$ be the 4-packing in $\mathcal{H}$ from Figure 2. Note that $d(X_4) = 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 $\mathcal{H}$ if we translate $X_4$ ten times.

**Proposition 3.3.** Let $k > 0$ and $m > 0$ be integers. There exist:

1. $k^2 p_{1,k}$-packings, $p_{1,k} = (5k-1)$, that form a partition of $X_4$;

2. $2k^2 p_{2,k}$-packings, $p_{2,k} = (6k-1)$, that form a partition of $X_4$;

3. $3k^2 p_{3,k}$-packings, $p_{3,k} = (8k-1)$, that form a partition of $X_4$;

4. $6k^2 p_{4,k}$-packings, $p_{4,k} = (11k-1)$, that form a partition of $X_4$;

5. $m^2 p_{j,mk}$-packings that form a partition of a $p_{j,k}$-packing from Point *j*, for $j \in \{1, \dots, 4\}$;

6. two $(5 \times 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 \times 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 $\mathbb{Z}^2$

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 $X_2 = \{(2x + y, x + 3y) | x \in \mathbb{Z}, y \in \mathbb{Z}\}$ be the maximized 2-packing in $\mathbb{Z}^2$ from Figure 4. Note that $d(X_2) = 1/A(2) = 1/5$ and that five 2-packings form a partition of $\mathbb{Z}^2$ if we translate $X_2$ four times.
<figure><img src="image_6.png" /><figcaption>Figure 4: The sets $X_2$ (2-packing), $X_3$ (3-packing) and $X_4$ (4-packing) in $\mathbb{Z}^2$.</figcaption></figure>

**Proposition 3.4.** Let $k > 0$, $m > 0$ be integers. There exist:

1. $k^2 (3k - 1)$-packings that form a partition of $X_2$;

2. $2k^2 (4k - 1)$-packings that form a partition of $X_2$;

3. two $(3 \times 2k - 1)$-packings that form a partition of a $(4k - 1)$-packing from Point 2;

4. two $(4k - 1)$-packings that form a partition of a $(3k - 1)$-packing from Point 1;

5. $m^2 (3mk - 1)$-packings that form a partition of a $(3k - 1)$-packing from Point 1;

6. $m^2 (4mk - 1)$-packings that form a partition of a $(4k - 1)$-packing from Point 2.

*Proof*. See Table B.6. □

<figure><img src="image_7.png" /></figure>

**3.5 Subdivision of a 3-packing in $\mathbb{Z}^2$**

Let $X_3 = \{(2x + 4y, 2y) | x \in \mathbb{Z}, y \in \mathbb{Z}\}$ be the maximized 3-packing in $\mathbb{Z}^2$ from Figure 4. Note that $d(X_3) = 1/A(3) = 1/8$ and that eight 3-packings form a partition of $\mathbb{Z}^2$ if we translate $X_3$ seven times.

**Proposition 3.5.** Let $k > 0$ and $m > 0$ be integers. There exist:

1. $k^2 (4k - 1)$-packings that form a partition of $X_3$;

2. $m^2 (4mk - 1)$-packings that form a partition of a $(4k - 1)$-packing from Point 1.

*Proof*. See Table B.6. □

<figure><img src="image_8.png" /></figure>
<figure><img src="image_9.png" /><figcaption>Figure 5: The sets $X_1$ (1-packing), $X_2$ (2-packing) and $X_3$ (3-packing) in $\mathcal{T}$.</figcaption></figure>

## 3.6 Subdivision of a 4-packing in $\mathbb{Z}^2$

Let $X_4 = \{(3x + 8y, 2x + y) | x \in \mathbb{Z}, y \in \mathbb{Z}\}$ be the maximized 4-packing in $\mathbb{Z}^2$ from Figure 4. Note that $d(X_4) = 1/A(4) = 1/13$ and that thirteen 4-packings form a partition of $\mathbb{Z}^2$ if we translate $X_4$ twelve times.

**Proposition 3.6.** Let $k > 0, m > 0$ be integers. There exist:

1. $k^2 (5k - 1)$-packings that form a partition of $X_4$;

2. $2k^2 (6k - 1)$-packings that form a partition of $X_4$;

3. two $(5 \times 2k - 1)$-packings that form a partition of a $(6k - 1)$-packing from Point 2;

4. two $(6k - 1)$-packings that form a partition of a $(5k - 1)$-packing from Point 1;

5. $m^2 (5mk - 1)$-packings that form a partition of a $(5k - 1)$-packing from Point 1;

6. $m^2 (6mk - 1)$-packings that form a partition of a $(6k - 1)$-packing from Point 2.

*Proof.* See Table B.6. □

<figure><img src="image_10.png" /></figure>

## 3.7 Subdivision of an independent set in $\mathcal{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 $X_1 = \{(x + 3y, x) | x \in \mathbb{Z}, y \in \mathbb{Z}\}$ be the (unique) maximized independent set (1-packing) in $\mathcal{T}$ from Figure 5. Note that $d(X_1) = 1/A(1) = 1/3$ and that three independent sets form a partition of $\mathcal{T}$ if we translate $X_1$ two times.

**Proposition 3.7.** Let $k > 0$ and $m > 0$ be integers. There exist:
1. $k^2 (2k-1)$-packings that form a partition of $X_1$;

2. $3k^2 (3k-1)$-packings that form a partition of $X_1$;

3. three $(3k-1)$-packings that form a partition of a $(2k-1)$-packing from Point 1;

4. $m^2 (2mk-1)$-packings that form a partition of a $(2k-1)$-packing from Point 1;

5. $m^2 (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 $\mathcal{T}$

Let $X_2 = \{(2x - y, x + 3y) | x \in \mathbb{Z}, y \in \mathbb{Z}\}$ be the maximized 2-packing in $\mathcal{T}$ from Figure 5. Note that $d(X_2) = 1/A(2) = 1/7$ and that seven 2-packings form a partition of $\mathcal{T}$ if we translate $X_2$ six times.

**Proposition 3.8.** Let $k > 0$ and $m > 0$ be integers. There exist:

1. $k^2 (3k-1)$-packings that form a partition of $X_2$;

2. $m^2 (3mk-1)$-packings that form a partition of a $(3k-1)$-packing from Point 1.

*Proof.* See Table B.7. □

## 3.9 Subdivision of a 3-packing in $\mathcal{T}$

Let $X_3 = \{(2x + 6y, 2x) | x \in \mathbb{Z}, y \in \mathbb{Z}\}$ be the maximized 3-packing in $\mathcal{T}$ from Figure 5. Note that $d(X_3) = 1/A(3) = 1/12$ and that twelve 3-packings form a partition of $\mathcal{T}$ if we translate $X_3$ eleven times.

**Proposition 3.9.** Let $k > 0$ and $m > 0$ be integers. There exist:

1. $k^2 (4k-1)$-packings that form a partition of $X_3$;

2. $3k^2 (6k-1)$-packings that form a partition of $X_3$;

3. three $(4 \times 3k-1)$-packings that form a partition of a $(6k-1)$-packing from Point 1;

4. $m^2 (4mk-1)$-packings that form a partition of a $(4k-1)$-packing from Point 1;

5. $m^2 (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 i-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 $a_0 = 1$. If $s_1 = 2$ and there exist three integers $1 < a_1 < \dots < a_3$ and three integers $k_1, \dots, k_3$ such that $s_{a_i} \le 3k_i - 1$ and $a_i - a_{i-1} \ge k_i^2$ or $s_{a_i} \le 4k_i - 1$ and $a_i - a_{i-1} \ge 2k_i^2$ for $i \in \{1, \dots, 3\}$ then $\chi_{\rho}^S(\mathcal{H}) \le a_3$.

This corollary can be useful to find upper bounds for a given sequence. For example, if $S = (2, 2, 2, 2, \dots)$, then taking $a_1 = 2$, $a_2 = 3$ and $a_3 = 4$, Corollary 4.1 gives us $\chi_{\rho}^S(\mathcal{H}) \le 4$ (this result is in fact treated in next subsection). Similarly, for the sequence $S = (2, 3, 3, 5, 5, 5, 5, 7, 7, 7, 7, 7, 7, 7, \dots)$, then taking $a_1 = 3$, $a_2 = 7$ and $a_3 = 15$, Corollary 4.1 gives us $\chi_{\rho}^S(\mathcal{H}) \le 15$. There are similar results for $s_1 = 3$ or $s_1 = 4$ using Propositions 3.3 and 3.4. For the two remaining lattices, the two following properties are given for $\mathbb{Z}^2$ with $s_1 = 2$ and for $\mathcal{T}$ with $s_1 = 1$. There exist similar properties for $\mathbb{Z}^2$ with $s_1 = 3$ or 4 using Propositions 3.5 and 3.6 and for $\mathcal{T}$ with $s_1 = 2$ or 3 using Propositions 3.8 and 3.9.

**Corollary 4.2.** Let $a_0 = 1$. If $s_1 = 2$ and there exist four integers $1 < a_1 < \dots < a_4$ and four integers $k_1, \dots, k_4$ such that $s_{a_i} \le 3k_i - 1$ and $a_i - a_{i-1} \ge k_i^2$ or $s_{a_i} \le 4k_i - 1$ and $a_i - a_{i-1} \ge 2k_i^2$ for $i \in \{1, \dots, 4\}$ then $\chi_{\rho}^S(\mathbb{Z}^2) \le a_4$.

**Corollary 4.3.** Let $a_0 = 1$. If $s_1 = 1$ and there exist two integers $1 < a_1 < a_2$ and two integers $k_1$ and $k_2$ such that $s_{a_i} \le 2k_i - 1$ and $a_i - a_{i-1} \ge k_i^2$ or $s_{a_i} \le 3k_i - 1$ and $a_i - a_{i-1} \ge 3k_i^2$ for $i \in \{1, \dots, 2\}$ then $\chi_{\rho}^S(\mathcal{T}) \le a_2$.

## 4.2 S-packing chromatic number and distance coloring

Jacko and Jendrol [10], Fertin et al. [2] and Ševciková [13] have studied distance colorings of $\mathcal{H}$, $\mathbb{Z}^2$ and $\mathcal{T}$ respectively. The following propositions come 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 $s_1 = d$, $s_n = d$ and $\chi_{\rho}^S(\mathcal{H}) = n$ is given by

$$n = \begin{cases} \lfloor \frac{3}{2}(d+1)^2 \rfloor & \text{for } d \text{ odd;} \\ \lfloor \frac{5}{8}(d+4/3)^2 \rfloor & \text{for } d \text{ even.} \end{cases}$$

**Proposition 4.5 ([2]).** Let $n$ and $d$ be integers. The minimum $n$ such that $s_1 = d$, $s_n = d$ and $\chi_{\rho}^S(\mathbb{Z}^2) = n$ is given by

$$n = \begin{cases} \frac{1}{2}(d+1)^2 & \text{for } d \text{ odd;} \\ \frac{1}{2}((d+1)^2 + 1) & \text{for } d \text{ even.} \end{cases}$$
**Proposition 4.6 ([13]).** Let $n$ and $d$ be integers. The minimum $n$ such that $s_1 = d$, $s_n = d$ and $\chi_{\rho}^S(\mathcal{H}) = n$ is given by

$$n = \left\lceil \frac{3}{4}(d+1)^2 \right\rceil.$$

# 5 $(d, n)$-packing chromatic number

## 5.1 Hexagonal lattice

**Proposition 5.1.** $\chi_{\rho}^{2,1}(\mathcal{H}) = \infty$, $\chi_{\rho}^{5,2}(\mathcal{H}) = \infty$, $\chi_{\rho}^{8,3}(\mathcal{H}) = \infty$, $\chi_{\rho}^{11,4}(\mathcal{H}) = \infty$, $\chi_{\rho}^{13,5}(\mathcal{H}) = \infty$ and $\chi_{\rho}^{16,6}(\mathcal{H}) = \infty$.

*Proof.* Let $\mathcal{H}$ be the hexagonal lattice and $k$ be an integer, $k \ge 16$.

$$\sum_{i=1}^{k} \frac{1}{A(i)} = \sum_{i=1}^{n} \frac{1}{A(2i)} + \sum_{i=0}^{n} \frac{1}{A(4i+1)} + \sum_{i=0}^{k} \frac{1}{A(4i+3)} = \sum_{i=1}^{k} \frac{1}{\frac{3}{2}i^2 + \frac{3}{2}i + 1} + \sum_{i=0}^{k} \frac{1}{6i^2 + 6i + 2} + \\ \sum_{i=0}^{k} \frac{1}{6i^2 + 12i + 6} < \frac{2}{15}\sqrt{15\pi} \tanh\left(\frac{1}{6}\pi\sqrt{15}\right) + \frac{1}{6}\sqrt{3\pi} \tanh\left(\frac{1}{6}\pi\sqrt{3}\right) + \frac{1}{36}\pi^2 - 1 < 1.494.$$

$$\text{Therefore: } \sum_{i=2}^{k} \frac{1}{A(i)} < 1.494 - \frac{1}{A(1)} < 0.994 < 1, \sum_{i=5}^{k} \frac{2}{A(i)} < 2(1.494 - \sum_{i=1}^{4} \frac{1}{A(i)}) < 0.955 < 1, \sum_{i=8}^{k} \frac{3}{A(i)} < 3(1.494 - \sum_{i=1}^{7} \frac{1}{A(i)}) < 0.935 < 1, \sum_{i=11}^{k} \frac{4}{A(i)} < 4(1.494 - \sum_{i=1}^{10} \frac{1}{A(i)}) < 0.925 < 1 \text{ and } \sum_{i=13}^{k} \frac{5}{A(i)} < 5(1.494 - \sum_{i=1}^{12} \frac{1}{A(i)}) < 0.986 < 1, \sum_{i=16}^{k} \frac{6}{A(i)} < 6(1.494 - \sum_{i=1}^{15} \frac{1}{A(i)}) < 0.968 < 1. \text{ Corollary 2.3 allows us to conclude. } \square$$

**Proposition 5.2.** $\chi_{\rho}^{2,2}(\mathcal{H}) \le 8$, $\chi_{\rho}^{2,3}(\mathcal{H}) \le 5$ and $\forall n \ge 4$, $\chi_{\rho}^{2,n}(\mathcal{H}) = 4$.

*Proof.* Using Proposition 3.1, we define a $(2, n)$-packing coloring of $\mathcal{H}$ for each $n = 2, 3$ and $n \ge 4$. $\mathcal{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 $\chi_{\rho}^{2,2}(\mathcal{H}) \le 8$. $\mathcal{H}$ can be partitioned into four 2-packings, the first three ones can be colored by colors 2 and the third one by two colors 3, to conclude $\chi_{\rho}^{2,3}(\mathcal{H}) \le 5$. $\mathcal{H}$ can be partitioned into four 2-packings, hence $\forall n \ge 4$, $\chi_{\rho}^{2,n}(\mathcal{H}) = 4$. $\square$

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 $i$-packings ($A_i$ is an $i$-packing) and the symbol C refers to the associated colors we use for each $i$-packing. By $k \times A_i$ we mean we use $k$ $i$-packings, and by $k \times i$ we mean we use $k$ colors $i$. In the rest of the paper, similar proofs will be only described by a table using the same format than this one.
<table><thead><tr><th></th><th></th><th></th><th>X<sub>2</sub></th><th>X<sub>2</sub></th></tr></thead><tbody><tr><td rowspan="2">(2,2)-packing</td><td>P</td><td>2&times;X<sub>2</sub></td><td>2&times;A<sub>3</sub></td><td>4&times;A<sub>5</sub></td></tr><tr><td>C</td><td>2&times;2</td><td>2&times;3</td><td>2&times;4, 2&times;5</td></tr><tr><td rowspan="2">(2,3)-packing</td><td>P</td><td>3&times;X<sub>2</sub></td><td>X<sub>2</sub></td><td></td></tr><tr><td>C</td><td>3&times;2</td><td>2&times;A<sub>3</sub></td><td></td></tr></tbody></table>

**Proposition 5.3.** $\chi_{\rho}^{3,2}(\mathcal{H}) \le 35$, $\chi_{\rho}^{3,3}(\mathcal{H}) \le 13$, $\chi_{\rho}^{3,4}(\mathcal{H}) \le 10$, $\chi_{\rho}^{3,5}(\mathcal{H}) \le 8$ and $\forall n \ge 6$, $\chi_{\rho}^{3,n}(\mathcal{H}) = 6$.

*Proof.* Using Proposition 3.2, we define a (3, n)-packing coloring of $\mathcal{H}$ for each $n = 2, 3, 4, 5$ and $n \ge 6$. $\mathcal{H}$ can be partitioned into six 3-packings, hence $\forall n \ge 6$, $\chi_{\rho}^{3,n}(\mathcal{H}) = 6$. The other colorings are described in Table C.8. □

**Proposition 5.4.** $\chi_{\rho}^{4,3}(\mathcal{H}) \le 58$, $\chi_{\rho}^{4,4}(\mathcal{H}) \le 27$, $\chi_{\rho}^{4,5}(\mathcal{H}) \le 21$, $\chi_{\rho}^{4,6}(\mathcal{H}) \le 18$ and from [10] $\forall n \ge 11$, $\chi_{\rho}^{4,n}(\mathcal{H}) = 11$.

*Proof.* Using Proposition 3.3, we define a (4, n)-packing coloring of $\mathcal{H}$ for each $n = 3, 4, 5, 6$ and $n \ge 11$. $\mathcal{H}$ can be partitioned into eleven 4-packings. The other colorings are described in Table C.9. □

## 5.2 Square lattice

**Proposition 5.5.** $\chi_{\rho}^{2,1}(\mathbb{Z}^2) = \infty$, $\chi_{\rho}^{4,2}(\mathbb{Z}^2) = \infty$, $\chi_{\rho}^{6,3}(\mathbb{Z}^2) = \infty$, $\chi_{\rho}^{8,4}(\mathbb{Z}^2) = \infty$, $\chi_{\rho}^{10,5}(\mathbb{Z}^2) = \infty$ and $\chi_{\rho}^{12,6}(\mathbb{Z}^2) = \infty$.

*Proof.* Let $\mathbb{Z}^2$ be the square lattice and $k$ be an integer, $k \ge 12$.

$$ \sum_{i=1}^{k} \frac{1}{A(i)} = \sum_{i=1}^{k} \frac{1}{A(2i)} + \sum_{i=0}^{k} \frac{1}{A(2i+1)} = \sum_{i=1}^{k} \frac{1}{2i^2+2i+1} + \sum_{i=0}^{k} \frac{1}{2i^2+4i+2} < \frac{1}{2}\pi \tanh\left(\frac{1}{2}\pi\right) + \frac{1}{12}\pi^2 - 1 < 1.264. $$

$$ \text{Therefore: } \sum_{i=2}^{k} \frac{1}{A(i)} < 1.264 - \frac{1}{A(1)} < 0.764 < 1, \sum_{i=4}^{k} \frac{2}{A(i)} < 2(1.264 - \sum_{i=1}^{3} \frac{1}{A(i)}) < 0.877 < 1, \sum_{i=6}^{k} \frac{3}{A(i)} < 3(1.264 - \sum_{i=1}^{5} \frac{1}{A(i)}) < 0.917 < 1, \sum_{i=8}^{k} \frac{4}{A(i)} < 4(1.264 - \sum_{i=1}^{7} \frac{1}{A(i)}) < 0.938 < 1, \sum_{i=10}^{k} \frac{5}{A(i)} < 5(1.264 - \sum_{i=1}^{9} \frac{1}{A(i)}) < 0.951 < 1 \text{ and } \sum_{i=12}^{k} \frac{6}{A(i)} < 6(1.264 - \sum_{i=1}^{11} \frac{1}{A(i)}) < 0.959 < 1. \text{ Corollary 2.3 allows us to conclude. } \square $$

**Proposition 5.6.** $\chi_{\rho}^{2,2}(\mathbb{Z}^2) \le 20$, $\chi_{\rho}^{2,3}(\mathbb{Z}^2) \le 8$, $\chi_{\rho}^{2,4}(\mathbb{Z}^2) \le 6$ and $\forall n \ge 5$, $\chi_{\rho}^{2,n}(\mathbb{Z}^2) = 5$.

*Proof.* Using Proposition 3.4, we define a (2, n)-packing coloring of $\mathbb{Z}^2$ for each $n = 2, 3, 4$ and $n \ge 5$. $\mathbb{Z}^2$ can be partitioned into five 2-packings, hence $\forall n \ge 5$, $\chi_{\rho}^{2,n}(\mathbb{Z}^2) = 5$. The other colorings are described in Table C.10. □

Soukal and Holub [14] have proven that $\chi_{\rho}^{1,1}(\mathbb{Z}^2) \le 17$, and proposed a 24 × 24 pattern in order to color the square lattice. Their pattern is recalled in Figure 6.
<figure><img src="image_11.png" /><figcaption>Figure 6: A 24 × 24 pattern [14].</figcaption></figure>

**Proposition 5.7.** $\chi_{\rho}^{3,3}(\mathbb{Z}^2) \le 33$.

*Proof.* In the pattern of Figure 6, $B_i$ denotes the set of vertices colored by $i$. Note that $B_2$ and $B_3$ are both 3-packings. It can be seen that $B_{16} \cup B_{17}$ form a 11-packing and that four 7-packings form a partition of $B_2$ or $B_3$. In order to color $\mathbb{Z}^2$ starting with 3, we partition $B_1$ into sixteen $i$-packings, $2 \le i \le 17$ (since $B_1$ is $\bigcup_{i=2}^{17} B_i$ translated by the vector $(1,0)$). Let $B'_i$ denote a copy of $B_i$ translated by $(1,0)$. We use two colors 3 to color $B_2$ and $B_3$, and one color $i$ in order to color $B_i$ for $i \in [4,8]$. We color $B'_i$ by one color $i$, for $i \in [3,8]$ and $B'_2$ 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 $B_9$. We use two colors 9 in order to color $B_{16}$, $B'_{16}$, $B_{17}$ and $B'_{17}$. The remaining color 9 is used to color $B'_9$. We use two colors $i$ in order to color $B_i$ and $B'_i$ for $i \in [10,13]$. The remaining colors 10, 11, 12 and 13 are used to color $B_{14}$, $B'_{14}$, $B_{15}$ and $B'_{15}$. $\square$

**Proposition 5.8.** $\chi_{\rho}^{3,4}(\mathbb{Z}^2) \le 20$, $\chi_{\rho}^{3,5}(\mathbb{Z}^2) \le 17$, $\chi_{\rho}^{3,6}(\mathbb{Z}^2) \le 14$ and $\forall n \ge 8$, $\chi_{\rho}^{3,n}(\mathbb{Z}^2) = 8$.

*Proof.* Using Proposition 3.5, we define a $(3, n)$-packing coloring of $\mathbb{Z}^2$ for each $n = 4, 5, 6$ and $n \ge 8$. $\mathbb{Z}^2$ can be partitioned into eight 3-packings, hence $\forall n \ge 8$,
$\chi_{\rho}^{3,n}(\mathbb{Z}^2) = 8$. The other colorings are described in Table C.11. $\square$

<figure><img src="image_12.png" /></figure>

**Proposition 5.9.** $\chi_{\rho}^{4,4}(\mathbb{Z}^2) \le 56$, $\chi_{\rho}^{4,5}(\mathbb{Z}^2) \le 34$, $\chi_{\rho}^{4,6}(\mathbb{Z}^2) \le 28$ and $\forall n \ge 13$, $\chi_{\rho}^{4,n}(\mathbb{Z}^2) = 13$.

*Proof.* Using Proposition 3.6, we define a (4, n)-packing coloring of $\mathbb{Z}^2$ for each $n = 4, 5, 6$ and $n \ge 13$. $\mathbb{Z}^2$ can be partitioned into thirteen 4-packings, hence $\forall n \ge 13$, $\chi_{\rho}^{4,n}(\mathbb{Z}^2) = 13$. The other colorings are described in Table C.12. $\square$

<figure><img src="image_13.png" /></figure>

## 5.3 Triangular lattice

**Proposition 5.10.** $\chi_{\rho}^{1,1}(\mathcal{T}) = \infty$, $\chi_{\rho}^{3,2}(\mathcal{T}) = \infty$, $\chi_{\rho}^{4,3}(\mathcal{T}) = \infty$, $\chi_{\rho}^{5,4}(\mathcal{T}) = \infty$, $\chi_{\rho}^{7,5}(\mathcal{T}) = \infty$ and $\chi_{\rho}^{8,6}(\mathcal{T}) = \infty$.

*Proof.* Let $\mathcal{T}$ be the triangular lattice and $k$ be an integer, $k \ge 8$.

$$ \sum_{i=1}^{k} \frac{1}{A(i)} = \sum_{i=1}^{k} \frac{1}{A(2i)} + \sum_{i=0}^{k} \frac{1}{A(2i+1)} = \sum_{i=1}^{k} \frac{1}{3i^2+3i+1} + \sum_{i=0}^{k} \frac{1}{3i^2+6i+3} < \frac{1}{3}\sqrt{3}\pi \tanh\left(\frac{1}{6}\pi\sqrt{3}\right) + \frac{1}{18}\pi^2 - 1 < 0.854. $$

$$ \text{Therefore: } \sum_{i=1}^{k} \frac{1}{A(i)} < 0.854 < 1, \sum_{i=3}^{k} \frac{2}{A(i)} < 2(0.854 - \sum_{i=1}^{2} \frac{1}{A(i)}) < 0.755 < 1, \\ \sum_{i=4}^{k} \frac{3}{A(i)} < 3(0.854 - \sum_{i=1}^{3} \frac{1}{A(i)}) < 0.883 < 1, \sum_{i=5}^{k} \frac{4}{A(i)} < 4(0.854 - \sum_{i=1}^{4} \frac{1}{A(i)}) < 0.966 < 1, \\ \sum_{i=7}^{k} \frac{5}{A(i)} < 5(0.854 - \sum_{i=1}^{6} \frac{1}{A(i)}) < 0.887 < 1 \text{ and } \sum_{i=8}^{k} \frac{6}{A(i)} < 6(0.854 - \\ \sum_{i=1}^{7} \frac{1}{A(i)}) < 0.940 < 1. \text{ Corollary 2.3 allows us to conclude. } \square $$

<figure><img src="image_14.png" /></figure>

**Proposition 5.11.** $\chi_{\rho}^{1,2}(\mathcal{T}) \le 6$ and $\forall n \ge 3$, $\chi_{\rho}^{1,n}(\mathcal{T}) = 3$.

*Proof.* Using Proposition 3.7, we define a (1, n)-packing coloring of $\mathcal{T}$ for each $n = 2$ and $n \ge 3$. $\mathcal{T}$ can be partitioned into three independent sets, hence $\forall n \ge 3$, $\chi_{\rho}^{1,n}(\mathcal{T}) = 3$. The other coloring is described in the following table.

<table><tr><td rowspan="2">(1,2)-packing</td><td>P</td><td>2×X<sub>1</sub></td><td>X<sub>1</sub><br/>4×A<sub>3</sub></td></tr><tr><td>C</td><td>2×1</td><td>2×2, 2×3</td></tr></table>

<figure><img src="image_15.png" /></figure>

**Proposition 5.12.** $\chi_{\rho}^{2,4}(\mathcal{T}) \le 16$, $\chi_{\rho}^{2,5}(\mathcal{T}) \le 13$, $\chi_{\rho}^{2,6}(\mathcal{T}) \le 10$ and $\forall n \ge 7$, $\chi_{\rho}^{2,n}(\mathcal{T}) = 7$.

*Proof.* Using Proposition 3.8, we define a (2, n)-packing coloring of $\mathcal{T}$ for each $n = 4, 5, 6$ and $n \ge 7$. $\mathcal{T}$ can be partitioned into seven 2-packings, hence $\forall n \ge 7$, $\chi_{\rho}^{2,n}(\mathcal{T}) = 7$. The other colorings are described in Table C.13. $\square$

<figure><img src="image_16.png" /></figure>

**Proposition 5.13.** $\chi_{\rho}^{3,4}(\mathcal{T}) \le 72$, $\chi_{\rho}^{3,5}(\mathcal{T}) \le 38$, $\chi_{\rho}^{3,6}(\mathcal{T}) \le 26$ and $\forall n \ge 12$, $\chi_{\rho}^{3,n}(\mathcal{T}) = 12$.
*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 ∀*n* ≥ 12, χ<sub>*ρ*</sub><sup>3,*n*</sup>(*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, Z² 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), χ<sub>ρ</sub><sup>1,2</sup>(O) ≤ 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 χ<sub>ρ</sub><sup>S</sup> = k and
there is no S-packing k coloring where the s<sub>1</sub>-packing is maximized could be an
interesting result.

References

[1] J. Ekstein, J. Fiala, P. Holub, B. Lidický, The packing chromatic number of the square lattice is at least 12, arXiv:1003.2291v1 (2010).

[2] G. Fertin, E. Godard, A. Raspaud, Acyclic and *k*-distance coloring of the grid, *Information Processing Letters* **87** (2003), 51–58.

[3] J. Fiala, P. A. Golovach, Complexity of the packing coloring problem for trees, *Discrete Applied Mathematics* **158** (2010), 771–778.

[4] J. Fiala, S. Klavžar, B. Lidický, The packing chromatic number of infinite product graphs, *Europan Journal of Combinatorics* **30** (2009), 1101–1113.

[5] A. S. Finbow, 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, D. F. Rall, Broadcast Chromatic Numbers of Graphs, *Ars Combinatoria* **86** (2008), 33–49.

[8] W. Goddard, 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, *Discursosiones Mathematicae Graph Theory* **32** (2012), 795–806.
[10] P. Jacko, Stanislav Jendrol, Distance Coloring of the Hexagonal Lattice, *Discussiones Mathematicae Graph Theory* **25** (2005), 151–166.

[11] D. Korže, A. Vesel, On the packing chromatic number of square and hexagonal lattice, *Ars Mathematica Contemporanea* **7** (2014), 13–22.

[12] F. Kramer, H. Kramer, A survey on the distance-colouring of graphs, *Discrete Mathematics* **308** (2008), 422–426.

[13] A. Ševciková, Distant chromatic number of the planar graphs, *Manuscript* (2001).

[14] R. Soukal, P. Holub, A Note on Packing Chromatic Number of the Square Lattice, *The Electronic Journal of Combinatorics* **17** (2010), 447–468.

[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

$$ \tau(v) = a + b + 1 \pmod{2}. $$

As $\mathcal{H} = V_0 \cup V_1$ is a bipartite graph, the type of a vertex $v$ corresponds to the index of the set $V_i$ to which $v$ belongs.

**Proposition A.2 ([10]).** Let $v_1 = (a_1, b_1)$, $v_2 = (a_2, b_2)$ be two vertices of the hexagonal lattice and assume that $b_1 \ge b_2$. Then the distance between $v_1$ and $v_2$ is

$$ d(v_1, v_2) = \begin{cases} |a_1 - a_2| + |b_1 - b_2| & \text{if } |a_1 - a_2| \ge |b_1 - b_2|; \\ 2|b_1 - b_2| - \tau(v_1) + \tau(v_2) & \text{if } |a_1 - a_2| < |b_1 - b_2|. \end{cases} $$

**Exemple A.3.** The set $X_2$ from Figure 2 is a 2-packing in $\mathcal{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)) \ge \min(d((2(x+1)+4y, x+1), (2x+4y, x)), d((2x+4(y+1), x), (2x+4y, x))) = 3$, hence $X_2$ is a 2-packing. $\square$

**Claim A.4.** Let $v_1 = (a_1, b_1)$ and $v_2 = (a_2, b_2)$ be two vertices of the square lattice. Then the distance between $v_1$ and $v_2$ is

$$ d(v_1, v_2) = |a_1 - a_2| + |b_1 - b_2|. $$

**Exemple A.5.** The set $X_2$ from Figure 4 is a 2-packing in $\mathbb{Z}^2$.
*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 \text{ and } d((2x+y+1, x-1+3(y+1), (2x+y, x+3y)) = 4 > 2, \\ \text{to conclude } X_2 \text{ is a 2-packing.} \quad \square$$

**Claim A.6.** Let $v_1 = (a_1, b_1)$ and $v_2 = (a_2, b_2)$ be two vertices of the triangular lattice. Then the distance between $v_1$ and $v_2$ is

$$d(v_1, v_2) = \begin{cases} \max(|a_1 - a_2|, |b_1 - b_2|) & \text{if } ((a_1 \ge a_2) \land (b_1 \le b_2)) \lor ((a_1 \le a_2) \land (b_1 \ge b_2)); \\ |a_1 - a_2| + |b_1 - b_2| & \text{otherwise.} \end{cases}$$

**Exemple A.7.** The set $X_1$ from Figure 5 is an independent set in $\mathcal{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 \\ \text{and } d((x + 3(y + 1), x), (x + 3y, x)) = 3 > 1, \text{ to conclude } X_1 \text{ is an independent set.} \quad \square$$

## B Decomposition of an *i*-packing in the three lattices

<table><caption>Table B.4: Decomposition of $X_3$ in $\mathcal{H}$ into $i$-packings.</caption><thead><tr><th>$i$</th><th>Number of $i$-packings</th><th>Description of a $i$-packing</th><th>Family of translation vectors</th></tr></thead><tbody><tr><td>$4k-1$</td><td>$k^2$</td><td>$\{3kx + 6ky, kx\}$</td><td>$(3i + 6j, i)$<br>$i, j \in \{0, \dots, k-1\}$</td></tr><tr><td>$6k-1$</td><td>$3k^2$</td><td>$\{3kx + 6ky, 3kx\}$</td><td>$(3i + 6j, 3i + 2a)$<br>$i, j \in \{0, \dots, k-1\}, a \in \{0, 1, 2\}$</td></tr><tr><td>$10k-1$</td><td>$8k^2$</td><td>$\{6kx + 12ky, 4kx\}$</td><td>$(6i + 12j + 3b, 4i + 2a + b)$<br>$i, j \in \{0, \dots, k-1\},<br>a \in \{0, 1, 2, 3\}, b \in \{0, 1\}$</td></tr><tr><td>$18k-1$</td><td>$24k^2$</td><td>$\{12kx + 24ky, 6kx\}$</td><td>$(12i + 24j + 3b, 6i + 2a + b)$<br>$i, j \in \{0, \dots, k-1\},<br>a \in \{0, \dots, 5\}, b \in \{0, 1, 2, 3\}$</td></tr></tbody></table>

## C Decomposition and associated colors
<table><caption>Table B.5: Decomposition of $X_4$ in $\mathcal{H}$ into $i$-packings.</caption><thead><tr><th>i</th><th>Number of i-packings</th><th>Description of a i-packing</th><th>Family of translation vectors</th></tr></thead><tbody><tr><td>5k - 1</td><td>k<sup>2</sup></td><td>{3kx - ky, 2kx + 3ky}</td><td>(3i - j, 2i + 3j)<br>i, j ∈ {0, ..., k - 1}</td></tr><tr><td>6k - 1</td><td>2k<sup>2</sup></td><td>{7kx - ky, kx + 3ky}</td><td>(7i + 3a - j, i + 2a + 3j)<br>i, j ∈ {0, ..., k - 1}, a ∈ {0, 1}</td></tr><tr><td>8k - 1</td><td>3k<sup>2</sup></td><td>{7kx + 2ky, kx + 5ky}</td><td>(7i + 2j + 3a, i + 5j + 2a)<br>i, j ∈ {0, ..., k - 1}, a ∈ {0, 1, 2}</td></tr><tr><td>11k - 1</td><td>6k<sup>2</sup></td><td>{-2kx + 11ky, 6kx}</td><td>(-2i + 11j + 7a, 6i + a)<br>i, j ∈ {0, ..., k - 1}, a ∈ {0, ..., 5}</td></tr></tbody></table>

<table><caption>Table B.6: Decomposition of $X_2$, $X_3$ and $X_4$ in $\mathbb{Z}^2$ into $i$-packings.</caption><thead><tr><th></th><th>i</th><th>Number of i-packings</th><th>Description of a i-packing</th><th>Family of translation vectors</th></tr></thead><tbody><tr><td rowspan="2">X<sub>2</sub></td><td>3k - 1</td><td>k<sup>2</sup></td><td>{2kx - ky, kx + 2ky}</td><td>(2i - j, i + 2j)<br>i, j ∈ {0, ..., k - 1}</td></tr><tr><td>4k - 1</td><td>2k<sup>2</sup></td><td>{4kx + ky, 2kx + 3ky}</td><td>(4i + 2a + j, 2i + 2a + 3j)<br>i, j ∈ {0, ..., k - 1}, a ∈ {0, 1}</td></tr><tr><td>X<sub>3</sub></td><td>4k - 1</td><td>k<sup>2</sup></td><td>{2kx + 4ky, 2kx}</td><td>(2i + 4j, 2i)<br>i, j ∈ {0, ..., k - 1}</td></tr><tr><td rowspan="2">X<sub>4</sub></td><td>5k - 1</td><td>k<sup>2</sup></td><td>{3kx - 2ky, 2kx + 3ky}</td><td>(3i - 2j, 2i + 3j)<br>i, j ∈ {0, ..., k - 1}</td></tr><tr><td>6k - 1</td><td>2k<sup>2</sup></td><td>{6kx + ky, 4kx + 5ky}</td><td>(6i + j + 3a, 4i + 5j + 2a)<br>i, j ∈ {0, ..., k - 1}, a ∈ {0, 1}</td></tr></tbody></table>

<table><caption>Table B.7: Decomposition of $X_1$, $X_2$ and $X_3$ in $\mathcal{T}$ into $i$-packings.</caption><thead><tr><th></th><th>i</th><th>Number of i-packings</th><th>Description of a i-packing</th><th>Family of translation vectors</th></tr></thead><tbody><tr><td rowspan="2">X<sub>1</sub></td><td>2k - 1</td><td>k<sup>2</sup></td><td>{kx + 3ky, kx}</td><td>(i + 3j, i)<br>i, j ∈ {0, ..., k - 1}</td></tr><tr><td>3k - 1</td><td>3k<sup>2</sup></td><td>{3kx + 3ky, 3kx}</td><td>(3i + 3j + a, 3i + a)<br>i, j ∈ {0, ..., k - 1}, a ∈ {0, 1, 2}</td></tr><tr><td>X<sub>2</sub></td><td>3k - 1</td><td>k<sup>2</sup></td><td>{2kx + 7ky, kx}</td><td>(2i + 7j, i)<br>i, j ∈ {0, ..., k - 1}</td></tr><tr><td rowspan="2">X<sub>3</sub></td><td>4k - 1</td><td>k<sup>2</sup></td><td>{2kx + 6ky, 2kx}</td><td>(2i + 6j, 2i)<br>i, j ∈ {0, ..., k - 1}</td></tr><tr><td>6k - 1</td><td>3k<sup>2</sup></td><td>{6kx + 6ky, 6kx}</td><td>(6i + 6j + 2a, 6i + 2a)<br>i, j ∈ {0, ..., k - 1}, a ∈ {0, 1, 2}</td></tr></tbody></table>
<table><caption>Table C.8: Decomposition of $\mathcal{H}$ into 3-packings and associated colors.</caption><tbody><tr><td rowspan="2">(3,2)-packing</td><td>P</td><td>2×X<sub>3</sub></td><td>X<sub>3</sub></td><td>X<sub>3</sub></td><td>X<sub>3</sub></td><td>X<sub>3</sub></td></tr><tr><td>C</td><td>2×3</td><td>2×4, 5</td><td>2×6, 2×7</td><td>4×X<sub>9</sub>, 8×X<sub>15</sub></td><td>X<sub>5</sub>, 3×X<sub>11</sub>, 4×X<sub>17</sub>, 6×X<sub>23</sub></td></tr><tr><td rowspan="2">(3,3)-packing</td><td>P</td><td>3×X<sub>3</sub></td><td>X<sub>3</sub></td><td>X<sub>3</sub></td><td>X<sub>3</sub></td><td>X<sub>3</sub></td></tr><tr><td>C</td><td>3×3</td><td>3×4</td><td>3×5</td><td>4×X<sub>7</sub></td><td>5, 2×10, 2×11, 2×16, 2×17, 2×18, 2×19, 20</td></tr><tr><td rowspan="2">(3,4)-packing</td><td>P</td><td>4×X<sub>3</sub></td><td>X<sub>3</sub></td><td>X<sub>3</sub></td><td>X<sub>3</sub></td><td>X<sub>3</sub></td></tr><tr><td>C</td><td>4×3</td><td>3×4</td><td>4, 2×5</td><td>3×6, 7</td><td></td></tr><tr><td rowspan="2">(3,5)-packing</td><td>P</td><td>5×X<sub>3</sub></td><td>X<sub>3</sub></td><td>X<sub>3</sub></td><td>X<sub>3</sub></td><td>X<sub>3</sub></td></tr><tr><td>C</td><td>5×3</td><td>3×4</td><td></td><td></td><td></td></tr></tbody></table>

<table><caption>Table C.9: Decomposition of $\mathcal{H}$ into 4-packings and associated colors.</caption><tbody><tr><td rowspan="4">(4,3)-packing</td><td>P</td><td>3×X<sub>4</sub></td><td>X<sub>4</sub></td><td>2×X<sub>4</sub></td><td>2×X<sub>4</sub></td><td>X<sub>4</sub></td></tr><tr><td>C</td><td>3×4</td><td>2×5</td><td>6×A<sub>7</sub></td><td>A<sub>5</sub>, 6×A<sub>9</sub></td><td>6×A<sub>11</sub>, 4×A<sub>19</sub></td></tr><tr><td>P</td><td></td><td></td><td></td><td>X<sub>4</sub></td><td>X<sub>4</sub></td></tr><tr><td>C</td><td></td><td></td><td></td><td>9×A<sub>14</sub></td><td>11×A<sub>19</sub>, 10×A<sub>23</sub></td></tr><tr><td rowspan="2">(4,4)-packing</td><td>P</td><td>4×X<sub>4</sub></td><td>2×X<sub>4</sub></td><td>2×X<sub>4</sub></td><td>2×X<sub>4</sub></td><td>X<sub>4</sub></td></tr><tr><td>C</td><td>4×4</td><td>4×5</td><td>6×A<sub>7</sub></td><td>8×A<sub>9</sub></td><td>2×A<sub>7</sub>, 3×A<sub>14</sub></td></tr><tr><td rowspan="2">(4,5)-packing</td><td>P</td><td>5×X<sub>4</sub></td><td>2×X<sub>4</sub></td><td>3×X<sub>4</sub></td><td>X<sub>4</sub></td><td></td></tr><tr><td>C</td><td>5×4</td><td>4×5</td><td>9×A<sub>7</sub></td><td>A<sub>5</sub>, 2×A<sub>9</sub></td><td></td></tr><tr><td rowspan="2">(4,6)-packing</td><td>P</td><td>6×X<sub>4</sub></td><td>3×X<sub>4</sub></td><td>2×X<sub>4</sub></td><td></td><td></td></tr><tr><td>C</td><td>6×4</td><td>6×5</td><td>6×A<sub>7</sub></td><td></td><td></td></tr></tbody></table>
<table><caption>Table C.10: Decomposition of $\mathbb{Z}^2$ into 2-packings and associated colors.</caption><tbody><tr><td rowspan="2">(2,2)-packing</td><td>P</td><td>2×X<sub>2</sub></td><td>X<sub>2</sub></td><td>X<sub>2</sub></td><td>X<sub>2</sub></td></tr><tr><td>C</td><td>2×2</td><td>2×3</td><td>2×4, 2×5</td><td>6×A<sub>8</sub>, 6×A<sub>11</sub></td></tr><tr><td rowspan="2">(2,3)-packing</td><td>P</td><td>3×X<sub>2</sub></td><td>X<sub>2</sub></td><td>X<sub>2</sub></td><td></td></tr><tr><td>C</td><td>3×2</td><td>2×3</td><td>3, 2×4</td><td>2×6, 2×7, 2×8<br>2×9, 2×10, 2×11</td></tr><tr><td rowspan="2">(2,4)-packing</td><td>P</td><td>4×X<sub>2</sub></td><td>X<sub>2</sub></td><td></td><td></td></tr><tr><td>C</td><td>4×2</td><td>2×3</td><td></td><td></td></tr></tbody></table>

<table><caption>Table C.11: Decomposition of $\mathbb{Z}^2$ into 3-packings and associated colors.</caption><tbody><tr><td rowspan="2">(3,4)-packing</td><td>P</td><td>4×X<sub>3</sub></td><td>4×X<sub>3</sub></td></tr><tr><td>C</td><td>4×3</td><td>16×A<sub>7</sub><br>4×4, 4×5, 4×6, 4×7</td></tr><tr><td rowspan="2">(3,5)-packing</td><td>P</td><td>5×X<sub>3</sub></td><td>3×X<sub>3</sub></td></tr><tr><td>C</td><td>5×3</td><td>12×A<sub>7</sub><br>5×4, 5×5, 2×6</td></tr><tr><td rowspan="2">(3,6)-packing</td><td>P</td><td>6×X<sub>3</sub></td><td>2×X<sub>3</sub></td></tr><tr><td>C</td><td>6×3</td><td>8×A<sub>7</sub><br>6×4, 2×5</td></tr></tbody></table>

<table><caption>Table C.12: Decomposition of $\mathbb{Z}^2$ into 4-packings and associated colors.</caption><tbody><tr><td rowspan="2">(4,4)-packing</td><td>P</td><td>4×X<sub>4</sub></td><td>2×X<sub>4</sub></td><td>4×X<sub>4</sub></td><td>X<sub>4</sub></td><td>X<sub>4</sub></td><td>X<sub>4</sub></td></tr><tr><td>C</td><td>4×4</td><td>4×5</td><td>16×A<sub>9</sub></td><td>8×A<sub>11</sub></td><td>9×A<sub>14</sub></td><td>3×A<sub>14</sub>, 12×A<sub>17</sub></td></tr><tr><td rowspan="2">(4,5)-packing</td><td>P</td><td>5×X<sub>4</sub></td><td>2×X<sub>4</sub></td><td>5×X<sub>4</sub></td><td>X<sub>4</sub></td><td></td><td></td></tr><tr><td>C</td><td>5×4</td><td>4×5</td><td>A<sub>5</sub>, 18×A<sub>9</sub></td><td>2×A<sub>9</sub>,<br>4×A<sub>11</sub></td><td></td><td></td></tr><tr><td rowspan="2">(4,6)-packing</td><td>P</td><td>6×X<sub>4</sub></td><td>3×X<sub>4</sub></td><td>4×X<sub>4</sub></td><td></td><td></td><td></td></tr><tr><td>C</td><td>6×4</td><td>6×5</td><td>6×6, 6×7, 4×8</td><td></td><td></td><td></td></tr></tbody></table>
<table><caption>Table C.13: Decomposition of $\mathcal{T}$ into 2-packings and associated colors.</caption><tr><td rowspan="2">(2,4)-packing</td><td>P</td><td>4×X<sub>2</sub></td><td>3×X<sub>2</sub></td></tr><tr><td></td><td></td><td>12×A<sub>5</sub></td></tr><tr><td></td><td>C</td><td>4×2</td><td>4×3, 4×4, 4×5</td></tr><tr><td rowspan="2">(2,5)-packing</td><td>P</td><td>5×X<sub>2</sub></td><td>2×X<sub>2</sub></td></tr><tr><td></td><td></td><td>8×A<sub>5</sub></td></tr><tr><td></td><td>C</td><td>5×2</td><td>5×3, 3×4</td></tr><tr><td rowspan="2">(2,6)-packing</td><td>P</td><td>6×X<sub>2</sub></td><td>X<sub>2</sub></td></tr><tr><td></td><td></td><td>4×A<sub>5</sub></td></tr><tr><td></td><td>C</td><td>6×2</td><td>4×3</td></tr></table>

<table><caption>Table C.14: Decomposition of $\mathcal{T}$ into 3-packings and associated colors.</caption><tr><td rowspan="4">(3,4)-packing</td><td>P</td><td>4×X<sub>3</sub></td><td>2×X<sub>3</sub></td><td>2×X<sub>3</sub></td></tr><tr><td></td><td>6×A<sub>5</sub></td><td>8×A<sub>7</sub></td><td>2×A<sub>5</sub>, 12×A<sub>11</sub></td></tr><tr><td>C</td><td>4×3</td><td>4×4, 2×5</td><td>4×6, 4×7</td><td>2×5, 4×9, 4×10, 4×11</td></tr><tr><td></td><td></td><td></td><td>X<sub>3</sub></td><td>X<sub>3</sub></td></tr><tr><td rowspan="3">(3,5)-packing</td><td>P</td><td></td><td></td><td>16×A<sub>15</sub></td><td>4×A<sub>11</sub>, 20×A<sub>23</sub></td></tr><tr><td></td><td></td><td></td><td>4×12, 4×13</td><td>4×8, 4×16, 4×17</td></tr><tr><td></td><td></td><td></td><td>4×14, 4×15</td><td>4×18, 4×19, 4×20</td></tr><tr><td rowspan="3">(3,6)-packing</td><td>P</td><td>5×X<sub>3</sub></td><td>3×X<sub>3</sub></td><td>2×X<sub>3</sub></td><td>2×X<sub>3</sub></td></tr><tr><td></td><td></td><td>9×A<sub>5</sub></td><td>8×A<sub>7</sub></td><td>18×A<sub>11</sub></td></tr><tr><td>C</td><td>5×3</td><td>5×4, 4×5</td><td>5×6, 3×7</td><td>5, 2×7, 5×8, 5×9, 3×10</td></tr><tr><td rowspan="2"></td><td>P</td><td>6×X<sub>3</sub></td><td>4×X<sub>3</sub></td><td>2×X<sub>3</sub></td><td></td></tr><tr><td></td><td></td><td>12×A<sub>5</sub></td><td>8×A<sub>7</sub></td><td></td></tr><tr><td></td><td>C</td><td>6×3</td><td>6×4, 6×5</td><td>6×6, 2×7</td><td></td></tr></table>