A lower bound for the packing chromatic number of the Cartesian product of cycles

作者：Jacobs Yoland^*; Jonck Elizabeth; Joubert Ernst J

来源：Central European Journal of Mathematics, 2013, 11(7): 1344-1357.

DOI：10.2478/s11533-013-0237-5

• Graph
• Packing
• Chromatic
• Cartesian product
• Cycles
• Bounds

Let G = (V, E) be a simple graph of order n and i be an integer with i a parts per thousand yen 1. The set X (i) aS dagger V(G) is called an i-packing if each two distinct vertices in X (i) are more than i apart. A packing colouring of G is a partition X = {X (1), X (2), aEuro broken vertical bar, X (k) } of V(G) such that each colour class X (i) is an i-packing. The minimum order k of a packing colouring is called the packing chromatic number of G, denoted by chi(rho)(G). In this paper we show, using a theoretical proof, that if q = 4t, for some integer t a parts per thousand yen 3, then 9 a parts per thousand currency sign chi(rho)(C (4) a- C (q) ). We will also show that if t is a multiple of four, then chi(rho)(C (4) a- C (q) ) = 9.

• 出版日期2013-7