ARS MATHEMATICA CONTEMPORANEA Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.) ARS MATHEMATICA CONTEMPORANEA 7 (2014) 13-22 On the packing chromatic number of square and hexagonal lattice* Danilo Korže FERI, University of Maribor, Smetanova 17, SI-2000 Maribor, Slovenia Aleksander Veself Faculty of Natural Sciences and Mathematics, University of Maribor Koroška cesta 160, SI-2000 Maribor, Slovenia Received 20 October 2011, accepted 31 October 2012, published online 7 January 2013 The packing chromatic number xP(G) of a graph G is the smallest integer k such that the vertex set V(G) can be partitioned into disjoint classes Xi,..., Xk, with the condition that vertices in Xj have pairwise distance greater than i. We show that the packing chromatic number for the hexagonal lattice H is 7. We also investigate the packing chromatic number for infinite subgraphs of the square lattice Z2 with up to 13 rows. In particular, we establish the packing chromatic number for P60Z and provide new upper bounds on these numbers for the other subgraphs of interest. Finally, we explore the packing chromatic number for some infinite subgraphs of Z2DP2. The results are partially obtained by a computer search. Keywords: Packing chromatic number, hexagonal lattice, square lattice, computer search. Math. Subj. Class.: 05C70, 05C85 1 Introduction and preliminaries The packing coloring was introduced by Goddard et al. in [6] under the name broadcast coloring. The concept comes from the regulations concerning the assignment of broadcast frequencies to radio stations. In particular, two radio stations which are assigned the same frequency must be placed sufficiently far apart so that neither broadcast interferes with the reception of the other. Moreover, the geographical distance between two radio stations * Supported by the Ministry of Science of Slovenia under the grant 0101-P-297. t Corresponding author. E-mail addresses: korze@uni-mb.si (Danilo Korze), vesel@uni-mb.si (Aleksander Vesel) Abstract ©® This work is licensed under http://creativecommons.Org/licenses/by/3.0/ 14 Ars Math. Contemp. 7 (2014) 41-54 which are assigned the same frequency is directly related to the power of their broadcast signals. These frequency restrictions have inspired the graphical coloring problem defined below. A k-coloring of a graph G is a function f from V(G) onto a set C = {1,2,..., k} (with no additional constraints). The elements of C are called colors. Let Xj denote the set of vertices with the image (color) i. Note that X1,..., Xk is partition of the vertex set of G into disjoint (color) classes. Let Xi,..., Xk be a partition of the vertex set of G with respect to the following constraints: each color class Xj is a set of vertices with the property that any distinct pair u, v e Xj satisfies dG(u, v) > i. Here dG(u, v) denotes the usual shortest path distance between u and v. Then Xj is said to be an i-packing, while such a partition is called a packing k-coloring. The smallest integer k for which there exists a packing k-coloring of G is called the packing chromatic number of G and it is denoted by xP (G). Let G = (V, E) be a graph. A walk is a sequence of vertices v1, v2,..., vk and edges vjvj+1, 1 < i < k - 1. A path on n vertices is a walk on n distinct vertices and denoted Pn. A walk is closed if v1 = vn. A closed walk in which all vertices (except the first and the last) are different, is a cycle. The cycle on n vertices is denoted Cn. For u, v e V(G), dG (u, v) or d(u, v) denotes the length of the shortest walk (i.e., the number of edges on the shortest walk) in G from u to v. These definitions extend naturally to directed graphs. A set S C V(G) is independent if xy e E(G) for any pair of vertices x,y e S. Cardinality of a largest independent set S of G is the independence number a(G) of G. This paper studies the packing chromatic number of hexagonal lattice and of some infinite subgraphs of square lattice. Section 2 contains the search for the lower bound on the packing chromatic number in hexagonal lattice. The bound is obtained by a computer program using the dynamic approach for computing graph invariants, as described in the first part of the section. Section 3 discusses the packing chromatic number for some infinite subgraphs of the square lattice. We establish the packing chromatic number for P6DZ and provide upper bounds on these numbers for P„DZ, where 7 < n < 13. We conclude the paper with the packing chromatic number for C4DZ as well as with some partial results on upper bounds for some infinite subgraphs of Z2DP2 provided in Section 4. The results in our paper were partially obtained by computers, mainly in Windows environment, but some also using Linux Ubuntu operating system. The machines used for computations were also diverse: Intel i7 930 based personal computer, Intel Q9400 based machine and a computer cluster (with up to 24 processor cores). All computations were carried out during six months, starting in the middle of 2010. The development environment and class libraries Lazarus (version of Pascal language) were used to write all necessary programs. 2 Hexagonal lattice The hexagonal lattice H plays a crucial role in many network applications, particularly in frequency assignments, e.g. see [5]. It was proved by Bresar et al. [1] that the packing chromatic number of the infinite hexagonal lattice lies between 6 and 8. The result was improved by Fiala et al. [3], where the packing 7-coloring of the hexagonal lattice is presented. We show in this section that actual lower bound on the packing chromatic number of the infinite hexagonal lattice is 7 and therefore xP(H) = 7. D. Korze and A. Vesel: On the packing chromatic number of square and hexagonal lattice 15 We now present the algorithms, that have been used to provide the main result. We first describe the concept needed to describe our computer checking. The idea is introduced in [9] in a more general framework, but for our purposes the following description will be sufficient. Figure 1: Graph Hi. Observe first the graph Hi depicted in Fig. 1. We construct H for i > 1 as follows. Take the graph which is composed of an isomorphic copy of Hi-i and of an isomorphic copy of Hi. Then add additional four edges that connect vertices u', v', w', and z' of the last added copy of Hi in Hi-i with the vertices u, v, w, and z of the new copy of Hi. As an example see Fig. 2 where H2 is depicted. Figure 2: Graph H2. Obviously, Hi is a subgraph of H for i > 1. We next define a directed graph Dk as follows. The vertices of Dk are all packing k-colorings of Hi. Let u and v be two distinct vertices of Dk. Then uV denotes a k-coloring of H2 such that u and v induce the respective packing k-coloring of the first and the second copy of Hi. Note that uV need not to be a packing k-coloring of H2. uv is an arc in Dk if and only if uV is a packing k-coloring of H2. Lemma 2.1. Let k < 6. Then Hi admits a packing k-coloring if and only if Dk possesses a walk P = vi,v2,..., vi with vj corresponding to the j-th copy of Hi. 16 Ars Math. Contemp. 7 (2014) 41-54 Proof. Suppose first that Dk possesses a walk P = vi, v2,..., v». If i — 2, then P is an arc from v1 to v2 in Dk and the claim is obvious. Let then i > 2. Suppose the claim holds for P' — vi, V2,..., Vj_i, i.e. Hj_i admits a packing k-coloring. Since P has an arc from vi-1 to vj, the corresponding colorings induce a packing k-coloring in a copy of H2 that corresponds to vj_1 and v». In order to see that the assertion holds, note that the distance between a vertex of a copy of H1 that corresponds to v» and a vertex of a copy of H1 that corresponds to vi-2 is at least 7. Suppose now that H admits a packing k-coloring. If i — 2, then by definition of Dk a packing k-coloring of H2 induce an arc in Dk. Let then i > 2. Note that H is composed of an isomorphic copy of Hj_1, say X, and of an isomorphic copy of H1, say Y. Y is connected in H to an isomorphic copy of H1, say Z. Suppose the claim holds for Hj_1 and let P' — v1, v2,..., vj_1 denote a walk in Dk that corresponds to X. Since H admits a packing k-coloring, Y induces a packing k-coloring of H1, say v». Y and Z together induce a packing k-coloring of H2 and therefore vi_1vi forms an arc in Dk. Then P — v1, v2,..., vi_1, v» is a walk in Dk and the proof is complete. □ Lemma 2.2. Let k < 6. Then H admits a packing k-coloring only if Dk contains a closed directed walk. Proof. Let H for a given k admit a packing k-coloring denoted f. Suppose that Dk is acyclic. Since H1 is finite, there is obviously only a finite number of vertices (packing k-colorings of H1) in Dk, say nk. Let then d < nk denotes the length of a longest directed path in Dk. Take now a subgraph of H isomorphic to Hd+2. A restriction of f to Hd+2 is obviously a packing k-coloring of Hd+2. From Lemma 2.1 it follows that Hd+2 admits a packing k-coloring if and only if Dk possesses a walk P — v1, v2,..., vd+2 with vj corresponding to a packing k-coloring of the j-th copy of H1. But since Dk is acyclic, the length of the longest walk in Dk is at most d and we obtain a contradiction. □ Theorem 2.3. xP(H) — 7. Proof. Since it is proved in [1] that the packing chromatic number of the infinite hexagonal lattice is at least 6 and since in [3] a coloring of the hexagonal lattice using 7 colors is presented, we have to show that H does not admit a packing 6-coloring. We first constructed the graph D6 by using a computer program. The graph consists of 26660 vertices with a maximum output degree of 37 (see also the concluding remark). By the depth first search algorithm we next established that D6 is an acyclic graph. From Lemma 2.2 then it follows that the hexagonal lattice cannot admit a packing 6-coloring. This assertion completes the proof. □ An alternative approach to prove Theorem 2.3 is to use a naive brute force search for a large enough subgraph of H. The approach used in the proof Theorem 2.3, however, is potentially much more interesting and utile in order to search for the packing chromatic number in other families of graphs since it uses the packing k-colorings of a relatively small graph. 3 Square lattice Cartesian product of graphs provide a setting which has been widely used in designing large scale computer systems and interconnection networks. The Cartesian product of graphs G D. Korze and A. Vesel: On the packing chromatic number of square and hexagonal lattice 17 and H is the graph GUH with vertex set V(G) x V(H) and (xi, x2)(yi, V2) € E(GUH) whenever x1y1 € E(G) and x2 = y2, or x2y2 € E(H) and x1 = y1. The Cartesian product is commutative and associative, having the trivial graph as a unit, cf. [8]. The subgraph of GUH induced by u x V(H) is isomorphic to H and it is called an H-fiber. It will be convenient to view the square lattice as the Cartesian product of two infinite paths, i.e ZUZ. Goddard et al. [6] determined the packing chromatic number for infinite subgraphs of the square lattice Z2 with up to 5 rows. In the same paper the question of determining the packing chromatic number of the infinite square lattice was posed. The best upper bound 17 was given by Holub and Soukal [7], while the best lower bound 12 was determined by Ekstein et al. [2]. We have considered infinite subgraphs of ZUZ with up to 13 rows. The main results are summarized in the following proposition. Proposition 3.1. (i) Xp(PeUZ) = 10, (ii) Xp(PrUZ) < 11, (iii) Xp(PsUZ) < 12, (iv) Xp(PqUZ) < 13, (v) Xp(P10UZ) < 14, (vi) Xp(PuUZ) < 14, (vii) Xp(P12UZ) < 15. (viii) Xp(P13UZ) < 15. Proof. Note first that if f is a packing k-coloring of PnUC^, k < t, then we can construct from f a packing k-coloring of PnUPm for every m. One can use f to color every Pn-fibre (uj x Pn) of PnUPm in the same way as the Pn-fibre (vj mod£ x Pn) of PnUC^ 1213121312131 10 31418151914121 16121312131715 21317141612131 19151213151814 312131 10 1213121 Figure 3: A packing 10-coloring of PeUC14 1 2 1 3 1 2 1 3 1 2 1 3 1 4 1 5 3 1 6 1 4 1 7 1 5 1 6 1 2 1 7 1 1 8 1 2 1 3 1 2 1 3 1 9 1 3 1 2 4 1 3 1 5 1 10 1 4 1 2 1 5 1 11 1 1 2 1 9 1 2 1 3 1 8 1 3 1 2 1 3 5 1 7 1 3 1 6 1 2 1 7 1 4 1 6 1 1 3 1 2 1 4 1 5 1 3 1 2 1 3 1 2 Figure 4: A packing 11-coloring of PtUC16 18 Ars Math. Contemp. 7 (2014) 41-54 1 2 1 3 1 2 1 3 1 2 1 3 1 4 3 1 5 1 4 1 10 1 11 1 5 1 2 1 1 8 1 2 1 3 1 2 1 3 1 6 1 9 2 1 3 1 6 1 5 1 4 1 7 1 3 1 1 4 1 7 1 2 1 3 1 2 1 12 1 5 3 1 2 1 3 1 9 1 8 1 3 1 2 1 1 11 1 5 1 4 1 2 1 5 1 4 1 10 2 1 3 1 2 1 3 1 6 1 2 1 3 1 Figure 5: A packing 12-coloring of P8DC14 1 2 1 3 1 2 1 3 1 2 1 3 1 2 1 3 1 2 1 3 4 1 5 1 6 1 4 1 5 1 7 1 4 1 5 1 6 1 7 1 1 3 1 2 1 3 1 2 1 3 1 2 1 3 1 2 1 3 1 2 12 1 8 1 7 1 10 1 11 1 6 1 9 1 13 1 4 1 5 1 1 2 1 3 1 2 1 3 1 2 1 3 1 2 1 3 1 2 1 3 6 1 4 1 9 1 5 1 4 1 8 1 5 1 7 1 10 1 11 1 1 3 1 2 1 3 1 2 1 3 1 2 1 3 1 2 1 3 1 2 7 1 5 1 13 1 6 1 7 1 12 1 4 1 6 1 5 1 4 1 1 2 1 3 1 2 1 3 1 2 1 3 1 2 1 3 1 2 1 3 Figure 6: A packing 13-coloring of P9\3C20 In order to obtained the upper bounds, we therefore first tried to find a packing k-coloring of PnDCm for every n of the interest with k (and m) being as small as possible. The obtained colorings for n G {6,7,8,9,11,13} are depicted in Figs. 3 - 8, while a packing 14-coloring of P10UC16 and a packing 15-coloring of P12\3C16 can be obtained from the first 10 rows of the packing 14-coloring of PhDCi6 depicted in Fig. 7 and the first 12 rows of the packing 15-coloring of Pi3II]Ci6 depicted in Fig. 8, respectively. In order to provide the lower bound for xp(P6DZ) we applied the backtracking search, e.g. see [10], adapted to packing colorings. Since the procedure did not find a packing 9-coloring in xp(P6DP12), the assertion follows. □ Results in Proposition 3.1 provide general upper bounds for infinite families of Cartesian products of two paths. For some graphs of these families however, better bounds or even the exact numbers can be computed. The results are depicted on the web page presented in the concluding remark. We again applied the backtracking search, which it is guaranteed to find a solution, if one exits, but it is relatively time consuming and therefore not usable for larger graphs. The colorings depicted in Figs. 3 - 8 have something in common: every second vertex in a row (column) is colored by the color 1. We therefore conjecture, that if a packing k-coloring of P„DPm exists, one can always find a packing k-coloring such that the class X1 is distributed as described above. This conjecture is formally stated below. Conjecture 3.2. Let n > 4 and let xP(PmOPn) = k. Then exists a packing k-coloring of PmUPn with |Xi | = a(PmDPn) = \nm 1. D. Korze and A. Vesel: On the packing chromatic number of square and hexagonal lattice 19 1 2 1 3 1 2 1 3 1 2 1 3 1 2 1 3 4 1 5 1 8 1 4 1 6 1 7 1 5 1 12 1 1 3 1 2 1 3 1 2 1 3 1 2 1 3 1 2 7 1 9 1 13 1 5 1 10 1 11 1 4 1 6 1 1 2 1 3 1 2 1 3 1 2 1 3 1 2 1 3 5 1 4 1 6 1 7 1 4 1 5 1 8 1 14 1 1 3 1 2 1 3 1 2 1 3 1 2 1 3 1 2 10 1 11 1 5 1 12 1 9 1 6 1 7 1 4 1 1 2 1 3 1 2 1 3 1 2 1 3 1 2 1 3 6 1 7 1 4 1 8 1 5 1 4 1 13 1 5 1 1 3 1 2 1 3 1 2 1 3 1 2 1 3 1 2 Figure 7: A packing 14-coloring of P11nC16 1 2 1 3 1 2 1 3 1 2 1 3 1 2 1 3 4 1 5 1 8 1 14 1 9 1 6 1 7 1 12 1 1 3 1 2 1 3 1 2 1 3 1 2 1 3 1 2 6 1 7 1 4 1 15 1 5 1 4 1 10 1 5 1 1 2 1 3 1 2 1 3 1 2 1 3 1 2 1 3 11 1 9 1 5 1 6 1 7 1 8 1 13 1 4 1 1 3 1 2 1 3 1 2 1 3 1 2 1 3 1 2 5 1 4 1 10 1 12 1 4 1 5 1 6 1 7 1 1 2 1 3 1 2 1 3 1 2 1 3 1 2 1 3 8 1 6 1 7 1 5 1 11 1 9 1 4 1 14 1 1 3 1 2 1 3 1 2 1 3 1 2 1 3 1 2 4 1 5 1 13 1 4 1 6 1 7 1 5 1 15 1 1 2 1 3 1 2 1 3 1 2 1 3 1 2 1 3 Figure 8: A packing 15-coloring of P13nC16 If the conjecture holds, the vertices of the class X1 can be fixed and therefore the backtracking is capable to provide results for much larger graph. In order to provide lower bounds for graphs of moderate size we therefore applied backtracking with no additional constraints, while for larger graphs the vertices of the class Xi were fixed. The results of these computations are summarized in Table 1. The results in the table are of two types: exact values and upper bounds. Some of the upper bounds are exact values of xP if the Conjecture 3.2 holds. If a value k in the table is exact, that means that a packing k-coloring for the graph of interest is found and that the backtracking procedure confirmed that a packing (k - 1)-coloring does not exist. An upper bound k means that a packing k-coloring for the graph of interest exists, but we could not prove that a packing (k - 1)-coloring does not exist. On the other hand, if an upper bound k is marked with asterisk, the backtracking proved that a packing (k - 1)-coloring with the vertices of the class X1 fixed as stated in the conjecture does not exist. 20 Ars Math. Contemp. 7 (2014) 41-54 m\n 6 7 8 9 10 11 12 13 14-15 16-24 25-27 28-41 > 41 6 8 9 9 9 9 9 10 10 10 10 10 10 10 7 9 9 9 10 10 10 10 10 < 11* < 11* < 11* < 11* 8 9 10 10 10 < 11* < 11* < 11* < 11* < 11* < 12 < 12 9 10 < 11* < 11* < 11* < 11* < 11* < 12* < 12* < 12* < 13 10 < 11* < 11* < 11* < 12* < 12* < 12* < 14 < 14 < 14 11 < 11* < 12* < 12* <14 < 14 < 14 < 14 < 14 12 < 12* < 12* <15 < 15 < 15 < 15 < 15 13 < 13 < 15 < 15 < 15 < 15 < 15 Table 1: Packing chromatic numbers and bounds for PmDPn. 4 Subgraphs of ZDZDP2 It is known that XP(Z3) = to [4]. Moreover even the packing chromatic number of ZDZDP2 is unbounded [3]. On the other hand, it was proved that xP(GDZ) < to for any finite graph G [3]. Hence, it is worthy to study the packing chromatic number of some infinite subgraphs of ZDZQP2. In particular we considered C4DZ, C6DZ, C8DZ, C10DZ, C12DZ, and P2DP3DZ. We were able to obtain exact results for the packing chromatic number of C4DZ, while for the other families some partial results and bounds were found. Proposition 4.1. (i) Xp(C4DZ) = 9, (ii) Xp(C6DZ) < 13, (iii) Xp(C8DZ) < 15, (iv) Xp (CioDZ) < 22, (v) Xp(Ci2DZ) < 17, (vi) Xp (P2QP3IDZ) < 18. Proof. The upper bounds follow from the packing 9-coloring of C4DC16 and from the packing 15-coloring of C8DC24 depicted in Fig 9 and Fig 10, respectively. The packing 13-coloring of C6DC48, the packing 22-coloring of C10DC48, the packing 17-coloring of C12DC48 and the packing 18-coloring of P2DP3DC48 can be obtained from the authors or from the web page presented in the concluding remark. 1416151814161519 2131213121312131 1517141915171418 3121312131213121 Figure 9: A packing 9-coloring of C4DCi6 The lower bound for C4QP10 is obtained by using the backtracking procedure which confirms that 8-coloring of C4QP10 does not exist. □ Note that a coloring of G which provides the upper bound in Proposition 4.1 has the vertices of the class X1 distributed such that the cardinality of X1 equals the independence number of G. We therefore generalize Conjecture 3.2 as follows. Let Xm denote Pm or Cm. D. Korze and A. Vesel: On the packing chromatic number of square and hexagonal lattice 21 1 13 1 8 1 4 1 5 1 9 1 4 1 5 1 8 1 4 1 5 1 9 1 4 3 1 2 1 3 1 2 1 3 1 2 1 3 1 2 1 3 1 2 1 3 1 2 1 1 6 1 7 1 12 1 14 1 6 1 7 1 13 1 15 1 6 1 7 1 10 1 5 2 1 3 1 2 1 3 1 2 1 3 1 2 1 3 1 2 1 3 1 2 1 3 1 1 4 1 9 1 5 1 4 1 8 1 5 1 4 1 9 1 5 1 4 1 8 1 11 3 1 2 1 3 1 2 1 3 1 2 1 3 1 2 1 3 1 2 1 3 1 2 1 1 5 1 15 1 6 1 7 1 10 1 11 1 6 1 7 1 12 1 14 1 6 1 7 2 1 3 1 2 1 3 1 2 1 3 1 2 1 3 1 2 1 3 1 2 1 3 1 Figure 10: A packing 15-coloring of C8UC24 Conjecture 4.2. Let n > 4 and let xP(XmOP£OPn) = k. Then there exists a packing k-coloring of XmOP£OPn such that |Xi| = a(XmOP£OPn). Analogous as in Section 3 we therefore applied backtracking with no additional constraints for graphs of moderate size, while for larger graphs the vertices of the class X1 were fixed. The packing colorings of the graphs of interest can be obtained from the authors or from the web page presented in the concluding remark. The results of these computations are summarized in Table 2, where an upper bound k marked with asterisk means that the backtracking proved that a packing (k - 1)-coloring with the vertices of the class X1 fixed as stated in the conjecture does not exist. m\n 2 3 4 5 6 7 8 9 10 11 12-15 16-18 19-34 > 34 4 5 5 7 7 7 7 8 8 9 9 9 9 9 9 6 5 8 8 8 10 10 11 11 11 12 < 12* < 12* < 13 < 13 8 7 7 9 9 10 10 11 < 12* < 12* < 13* < 13* < 14 < 14 < 15 P20P3 5 8 8 10 10 11 < 12* < 12* < 14 < 15 < 18 < 18 < 18 < 18 Table 2: Packing chromatic numbers for CmDP„ and P2nP3nPn (below). Concluding remark All obtained packing colorings as well as the graph D6 can be obtained from the authors or directly from the web page http://matematika-racunalnistvo.fnm. uni-mb.si/personal/vesel/constructions.aspx. Acknowledgments We would like to thank the referees for their careful reading and helpful suggestions. References [1] B. Bresar, S. Klavzar and D. F. Rall, On the packing chromatic number of Cartesian products, hexagonal lattice, and trees, Discrete Appl. Math. 155 (2007), 2303-2311. [2] J. Ekstein, J. Fiala, P. Holub and B. Lidicky, The packing chromatic number of the square lattice is at least 12, manuscript. 22 Ars Math. Contemp. 7 (2014) 41-54 [3] J. Fiala, S. KlavZar and B. Lidicky, The packing chromatic number of infinite product graphs, European J. ofCombin. 30 (2009), 1101-1113. [4] A. S. Finbow and D. F. Rail On the packing chromatic number of some lattices, Discrete Appl. Math. 158 (2010), 1224-1228. [5] A. Gamst, Some lower bounds for a class of frequency assignment problems, IEEE Trans. Veh. Technol. 35 (1986), 8-14. [6] W. Goddard, S. M. Hedetniemi, S. T. Hedetniemi, J. M. Harris and D. F. Rall, Broadcast chromatic numbers of graphs, Ars Combin. 86 (2008), 33-49. [7] P. Holub and R. Soukal, A note on packing chromatic number of the square lattice, Electron. J. Combin. 17 (2010), R#17. [8] W. Imrich and S. KlavZar, Product Graphs: Structure and Recognition, Wiley-Interscience, New York, 2000. [9] S. KlavZar and A. Vesel, Computing graph invariants on rotagraphs using dynamic algorithm approach: the case of (2,1)-colorings and independence numbers, Discrete Appl. Math. 129 (2003), 449-460. [10] A. Nijenhuis and H. S. Wilf, Combinatorial Algorithms, Academic Press, 1978.