pith. sign in

arxiv: 1707.04910 · v1 · pith:HWDJJGMPnew · submitted 2017-07-16 · 🧮 math.CO

Packing chromatic number versus chromatic and clique number

classification 🧮 math.CO
keywords numberchromaticpackingprovedgivengraphmycielskianrealizable
0
0 comments X
read the original 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.