Packing Coloring of Some Undirected and Oriented Coronae Graphs

Daouya Laïche, Isma Bouchemakh, and Éric Sopena. "Packing Coloring of Some Undirected and Oriented Coronae Graphs." Discussiones Mathematicae Graph Theory 37.3 (2017): 665-690. <http://eudml.org/doc/288517>.

@article{DaouyaLaïche2017,
abstract = {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.},
author = {Daouya Laïche, Isma Bouchemakh, Éric Sopena},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {packing coloring; packing chromatic number; corona graph; path; cycle},
language = {eng},
number = {3},
pages = {665-690},
title = {Packing Coloring of Some Undirected and Oriented Coronae Graphs},
url = {http://eudml.org/doc/288517},
volume = {37},
year = {2017},
}

TY - JOUR
AU - Daouya Laïche
AU - Isma Bouchemakh
AU - Éric Sopena
TI - Packing Coloring of Some Undirected and Oriented Coronae Graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2017
VL - 37
IS - 3
SP - 665
EP - 690
AB - 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.
LA - eng
KW - packing coloring; packing chromatic number; corona graph; path; cycle
UR - http://eudml.org/doc/288517
ER -