Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
5777005 | Discrete Mathematics | 2017 | 6 Pages |
Abstract
The packing chromatic number ÏÏ(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 and Togni (2016). In addition, the packing chromatic number is investigated with respect to several local operations. In particular, if Se(G) is the graph obtained from a graph G by subdividing its edge e, then ÏÏ(G)â2+1â¤ÏÏ(Se(G))â¤ÏÏ(G)+1.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Boštjan Brešar, Sandi Klavžar, Douglas F. Rall, Kirsti Wash,