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 {\displaystyle i} is greater than i {\displaystyle i} . The packing chromatic number (or broadcast chromatic number) χ ρ ( G ) {\displaystyle \chi _{\rho }(G)} (or χ b ( G ) {\displaystyle \chi _{b}(G)} ) of a graph G {\displaystyle G} is the minimum number of colors needed for a packing coloring.
Definition A packing coloring of a graph G = ( V , E ) {\displaystyle G=(V,E)} is a function π : V → { 1 , 2 , … , k } {\displaystyle \pi :V\to \{1,2,\ldots ,k\}} such that if π ( u ) = π ( v ) {\displaystyle \pi (u)=\pi (v)} , then the distance d ( u , v ) > π ( u ) {\displaystyle d(u,v)>\pi (u)} . The minimum k {\displaystyle k} for which such a coloring exists is the packing chromatic number χ ρ ( G ) {\displaystyle \chi _{\rho }(G)} . Equivalently, a packing coloring is a partition P π = { V 1 , V 2 , … , V k } {\displaystyle {\mathcal {P}}_{\pi }=\{V_{1},V_{2},\ldots ,V_{k}\}} of the vertex set where each V i {\displaystyle V_{i}} is an i {\displaystyle i} -packing (vertices at pairwise distance more than i {\displaystyle i} ).
Basic properties For any graph G {\displaystyle G} with n {\displaystyle n} vertices:
ω ( G ) ≤ χ ( G ) ≤ χ ρ ( G ) {\displaystyle \omega (G)\leq \chi (G)\leq \chi _{\rho }(G)} , where ω ( G ) {\displaystyle \omega (G)} is the clique number and χ ( G ) {\displaystyle \chi (G)} is the chromatic number
χ ρ ( G ) ≤ α 0 ( G ) + 1 {\displaystyle \chi _{\rho }(G)\leq \alpha _{0}(G)+1} , where α 0 ( G ) {\displaystyle \alpha _{0}(G)} is the vertex cover number, with equality if and only if G {\displaystyle G} has diameter two
χ ρ ( G ) ≤ n − α ( G ) + 1 {\displaystyle \chi _{\rho }(G)\leq n-\alpha (G)+1} , where α ( G ) {\displaystyle \alpha (G)} is the independence number If χ ρ ( G ) = χ ( G ) {\displaystyle \chi _{\rho }(G)=\chi (G)} , then ω ( G ) = χ ( G ) {\displaystyle \omega (G)=\chi (G)}
Complexity Determining whether χ ρ ( G ) ≤ 3 {\displaystyle \chi _{\rho }(G)\leq 3} can be solved in polynomial time, while determining whether χ ρ ( G ) ≤ 4 {\displaystyle \chi _{\rho }(G)\leq 4} is NP-hard, even for planar graphs. The problem remains NP-hard for diameter 2 graphs, since computing the vertex cover number is NP-hard for such graphs. The problem is NP-complete for trees, resolving a long-standing open question. However, it can be solved in polynomial time for graphs of bounded treewidth and bounded diameter.
Specific graph families For path graphs P n {\displaystyle P_{n}} :
χ ρ ( P n ) = 2 {\displaystyle \chi _{\rho }(P_{n})=2} for 2 ≤ n ≤ 3 {\displaystyle 2\leq n\leq 3}
… excerpt ends here. Continue reading the full article.
