Packing chromatic number versus chromatic and clique number

Abstract

The packing chromatic number ${\chi }_{\rho }(G)$ of a graph $G$ is the smallest integer $k$ such that the vertex set of $G$ can be partitioned into sets $V_i$, $i\in [k]$, where each $V_i$ is an $i$-packing. In this paper, we investigate for a given triple $(a,b,c)$ of positive integers whether there exists a graph $G$ such that $\omega (G)=a$, $\chi (G)=b$, and ${\chi }_{\rho }(G)=c$. If so, we say that $(a,b,c)$ is realizable. It is proved that $b=c\ge 3$ implies $a=b$, and that triples $(2,k,k+1)$ and $(2,k,k+2)$ are not realizable as soon as $k\ge 4$. Some of the obtained results are deduced from the bounds proved on the packing chromatic number of the Mycielskian. Moreover, a formula for the independence number of the Mycielskian is given. A lower bound on ${\chi }_{\rho }(G)$ in terms of $\Delta (G)$ and $\alpha (G)$ is also proved.

17 pages, 1 table