Packing Coloring of Some Undirected and Oriented Coronae Graphs

• Autorzy: Daouya Laïche , Isma Bouchemakh , Éric Sopena
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

packing coloring; packing chromatic number; corona graph; path; cycle

Kategorie tematyczne

• 05C05: Trees
• 05C15: Coloring of graphs and hypergraphs
• 05C70: Factorization, matching, partitioning, covering and packing

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2017
• Tom: 37
• Numer: 3
• Strony: 665-690

Daty

wydano

2017-08-01

otrzymano

2016-03-18

poprawiono

2016-06-06

zaakceptowano

2016-06-06

online

2017-07-06

Twórcy

autor

Daouya Laïche

• , , B.P. 32 El-Alia, Bab-Ezzouar, ,

autor

Isma Bouchemakh

• , , B.P. 32 El-Alia, Bab-Ezzouar, ,

autor

Éric Sopena

• , LaBRI, UMR5800, F-33400 Talence, ; CNRS, LaBRI, UMR5800, F-33400 Talence,

Identyfikatory

DOI

10.7151/dmgt.1963