Packing chromatic number versus chromatic and clique number

Boštjan Brešar, Sandi Klavžar, Douglas F. Rall, Kirsti Wash

Published 2017-07-16Version 1

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.