The packing chromatic number χρ(G) of a graph G is the smallest integer k such that its set of vertices V(G) can be partitioned into k disjoint subsets V1, . . . , Vk, in such a way that every two distinct vertices in Vi are at distance greater than i in G for every i, 1 ≤ i ≤ k. For a given integer p ≥ 1, the p-corona of a graph G is the graph obtained from G by adding p degree-one neighbors to every vertex of G. In this paper, we determine the packing chromatic number of p-coronae of paths and cycles for every p ≥ 1. Moreover, by considering digraphs and the (weak) directed distance between vertices, we get a natural extension of the notion of packing coloring to digraphs. We then determine the packing chromatic number of orientations of p-coronae of paths and cycles.
@article{bwmeta1.element.doi-10_7151_dmgt_1963,
author = {Daouya La\"\i che and Isma Bouchemakh and \'Eric Sopena},
title = {Packing Coloring of Some Undirected and Oriented Coronae Graphs},
journal = {Discussiones Mathematicae Graph Theory},
volume = {37},
year = {2017},
pages = {665-690},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1963}
}
Daouya Laïche; Isma Bouchemakh; Éric Sopena. Packing Coloring of Some Undirected and Oriented Coronae Graphs. Discussiones Mathematicae Graph Theory, Tome 37 (2017) pp. 665-690. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1963/