pith. sign in

arxiv: 1608.05577 · v1 · pith:YSMCBLCMnew · submitted 2016-08-19 · 🧮 math.CO

Packing chromatic number under local changes in a graph

classification 🧮 math.CO
keywords packingchromaticgraphnumbergraphslocaladditionanswering
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 there exists a $k$-vertex coloring of $G$ in which any two vertices receiving color $i$ are at distance at least $i+1$. It is proved that in the class of subcubic graphs the packing chromatic number is bigger than $13$, thus answering an open problem from [Gastineau, Togni, $S$-packing colorings of cubic graphs, Discrete Math.\ 339 (2016) 2461--2470]. In addition, the packing chromatic number is investigated with respect to several local operations. In particular, if $S_e(G)$ is the graph obtained from a graph $G$ by subdividing its edge $e$, then $\left\lfloor \chi_{\rho}(G)/2 \right\rfloor +1 \le \chi_{\rho}(S_e(G)) \le \chi_{\rho}(G)+1$.

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.