|
|||||
|
|
On the packing chromatic number of Cartesian products, hexagonal lattice, and trees |
|
| Authors: | Bo&scaron tjan Bre&scaron ar,Sandi Klav?ar,Douglas F. Rall |
| Affiliation: | a FEECS, University of Maribor, Smetanova 17, 2000 Maribor, Slovenia b Department of Mathematics and Computer Science, FNM, University of Maribor, Gosposvetska 84, 2000 Maribor, Slovenia c Department of Mathematics, Furman University, Greenville, SC, USA |
| Abstract: | The packing chromatic number χρ(G) of a graph G is the smallest integer k such that the vertex set of G can be partitioned into packings with pairwise different widths. Several lower and upper bounds are obtained for the packing chromatic number of Cartesian products of graphs. It is proved that the packing chromatic number of the infinite hexagonal lattice lies between 6 and 8. Optimal lower and upper bounds are proved for subdivision graphs. Trees are also considered and monotone colorings are introduced. |
| Keywords: | Packing chromatic number Cartesian product of graphs Hexagonal lattice Subdivision graph Tree Computational complexity |
| 本文献已被 ScienceDirect 等数据库收录！ | |