Packing coloring
In graph theory, a packing coloring (also called a broadcast coloring) is a type of graph coloring where vertices are assigned colors (represented by positive integers) such that the distance between any two vertices with the same color i…
≈ 4 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
In graph theory, a packing coloring (also called a broadcast coloring) is a type of graph coloring where vertices are assigned colors (represented by positive integers) such that the distance between any two vertices with the same color i is greater than i . The packing chromatic number (or broadcast chromatic number) \chi_\rho(G) (or \chi_b(G) ) of a graph G is the minimum number of colors needed for a packing coloring. A packing coloring of a graph G = (V,E) is a function \pi : V \to \{1,2,\ldots,k\} such that if \pi(u) = \pi(v) , then the distance d(u,v) > \pi(u) . The minimum k for which such a coloring exists is the packing chromatic number \chi_\rho(G) . Equivalently, a packing coloring is a partition \mathcal{P}_\pi = \{V_1, V_2, \ldots, V_k\} of the vertex set where each V_i is an i -packing (vertices at pairwise distance more than i ). If \chi_\rho(G) = \chi(G) , then \omega(G) = \chi(G) \chi_\rho(P_n) = 2 for 2 \leq n \leq 3 \chi_\rho(P_n) = 3 for n \geq 4 For cycle graphs C_n with n \geq 3 : \chi_\rho(C_n) = 3 if n is 3 or a multiple of 4 \chi_\rho(C_n) = 4 otherwise For trees T of order n : \chi_\rho(T) \leq (n+7)/4 for all trees except P_4 and two specific 8 -vertex trees The star graph K_{1,n-1} has \chi_\rho(K_{1,n-1}) = 2 Trees of diameter 3 have \chi_\rho(T) = 3 The bound (n+7)/4 is sharp and achieved by specific tree constructions For the hypercube graph Q_k \chi_\rho(Q_k) \sim \frac{1}{2} \cdot O(1/k) \cdot 2^k asymptotically With k = 1, 2, 3, 4 ...: \chi_\rho(Q_k) = 2, 3, 5, 7, 15, 25, 49, 95 ...
For complete graphs K_n : \chi_\rho(K_n) = n \chi_\rho(S(K_n)) = n + 1 for n \geq 3 For bipartite graphs G of diameter 3 : \alpha_0(G) \leq \chi_\rho(G) \leq \alpha_0(G) + 1 For complete multipartite graphs and wheel graphs G : \chi_\rho(G) = \alpha_0(G) + 1 For the r \times c grid graph G_{r,c} : \chi_\rho(G_{2,c}) = 5 for c \geq 6 \chi_\rho(G_{3,c}) = 7 for c \geq 12 \chi_\rho(G_{4,c}) = 8 for c \geq 10 \chi_\rho(G_{5,c}) = 9 for c \geq 10 \chi_\rho(G_{r,c}) \leq 23 for any finite grid For r = c = 1, 2, 3, 4 ... (the square grid graphs): \chi_\rho(G_{r,c}) = 1, 3, 4, 5, 7, 8, 9, 9, 10, 11 ...
The infinite square grid G_{\infty,\infty} has: \chi_\rho(G_{\infty,\infty}) = 15 The infinite hexagonal lattice H has: \chi_\rho(H) = 7 The infinite triangular lattice has infinite packing chromatic number. For the subdivision graph S(G) of a graph G , obtained by subdividing every edge once: For connected graphs G with at least 3 vertices: \omega(G) + 1 \leq \chi_\rho(S(G)) \leq \chi_\rho(G) + 1 For connected bipartite graphs with at least two edges: \chi_\rho(S(G)) = 3 A connected graph G has \chi_\rho(G) = 2 if and only if G is a star.
A graph has \chi_\rho(G) = 3 if and only if it can be formed by taking a bipartite multigraph, subdividing every edge exactly once, adding leaves to some vertices, and performing a single T -add operation to some vertices. Dominating broadcast: A function b : V \to \{0,1,\ldots\} where b(u) \leq e(u) (eccentricity) and every vertex with b(v) = 0 has a neighbor u with b(u) > 0 and d(u,v) \leq b(u) Broadcast independence: A broadcast where b(u), b(v) > 0 implies d(u,v) > b(u) S -packing coloring (or (s_1,s_2,\ldots,s_k) -coloring): For a non-decreasing sequence S = (s_1, s_2, \ldots) of positive integers, vertices in color class i must be at distance greater than s_i apart.
The standard packing coloring corresponds to S = (1, 2, 3, \ldots) . The S -packing chromatic number \chi_S(G) is the minimum number of colors needed.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1327511270 under CC BY-SA 4.0; modifications have been made.