314 KB21 KB200820252014Korže, DaniloVesel, Aleksanderštevilka:1letnik:7str. 13-22COBISSID:17063446ISSN:1855-3966URN:URN:NBN:SI:doc-APWJZCSBenDruštvo matematikov, fizikov in astronomov SlovenijeArs mathematica contemporaneacomputer searchgraph theoryhexagonal latticepacking chromatic numbersquare latticeteorija grafovOn the packing chromatic number of square and hexagonal lattice|The packing chromatic number ?$\chi_p(G)$? of a graph ?$G$? is the smallest integer ?$k$? such that the vertex set ?$V(G)$? can be partitioned into disjoint classes? $X_1, \dots , X_k$?, with the condition that vertices in ?$X_i$? have pairwise distance greater than ?$i$?. We show that the packing chromatic number for the hexagonal lattice ?$\mathcal{H}$? is 7. We also investigate the packing chromatic number for infinite subgraphs of the square lattice ?$\mathbb{Z}^2$? with up to 13 rows. In particular, we establish the packing chromatic number for ?$P_6 \Box \mathbb{Z}$? 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 ?$\mathbb{Z}^2 \Box P_2$?. The results are partially obtained by a computer searchTEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije