The packing chromatic number $$\chi _{\rho }(G)$$χρ(G) of a graph G is the smallest integer k such that the vertex set of G can be partitioned into sets $$\Pi _1,\ldots… Click to show full abstract
The packing chromatic number $$\chi _{\rho }(G)$$χρ(G) of a graph G is the smallest integer k such that the vertex set of G can be partitioned into sets $$\Pi _1,\ldots ,\Pi _k$$Π1,…,Πk, where $$\Pi _i$$Πi, $$i\in [k]$$i∈[k], is an i-packing. The following conjecture is posed and studied: if G is a subcubic graph, then $$\chi _{\rho }(S(G))\le 5$$χρ(S(G))≤5, where S(G) is the subdivision of G. The conjecture is proved for all generalized prisms of cycles. To get this result it is proved that if G is a generalized prism of a cycle, then G is (1, 1, 2, 2)-colorable if and only if G is not the Petersen graph. The validity of the conjecture is further proved for graphs that can be obtained from generalized prisms in such a way that one of the two n-cycles in the edge set of a generalized prism is replaced by a union of cycles among which at most one is a 5-cycle. The packing chromatic number of graphs obtained by subdividing each of its edges a fixed number of times is also considered.
               
Click one of the above tabs to view related content.