2015/06/24 by Daouya Laïche, Daouya, Laïche, Isma Bouchemakh +3 · 3 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1506.07248
openalex publication_date 2015/06/24 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28
The packing chromatic number \pcn(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 V_1, …, V_k, in such a way that every two distinct vertices in V_i are at distance greater than i in G for every i, 1≤ i≤ k. For a given integer p ≥ 1, the generalized corona G\odot pK_1 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 generalized coronae of paths and cycles. 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 generalized coronae of paths and cycles.