Geodesic
Packing Coloring of Some Undirected and Oriented Coronae Graphs
Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 3, pp. 665-690.

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: packing coloring, packing chromatic number, corona graph, path, cycle 
@article{DMGT_2017_37_3_a12,
     author = {La{\"\i}che, Daouya and Bouchemakh, Isma and Sopena, \'Eric},
     title = {Packing {Coloring} of {Some} {Undirected} and {Oriented} {Coronae} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {665--690},
     publisher = {mathdoc},
     volume = {37},
     number = {3},
     year = {2017},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2017_37_3_a12/}
}
TY  - JOUR
AU  - Laïche, Daouya
AU  - Bouchemakh, Isma
AU  - Sopena, Éric
TI  - Packing Coloring of Some Undirected and Oriented Coronae Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2017
SP  - 665
EP  - 690
VL  - 37
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2017_37_3_a12/
LA  - en
ID  - DMGT_2017_37_3_a12
ER  - 
%0 Journal Article
%A Laïche, Daouya
%A Bouchemakh, Isma
%A Sopena, Éric
%T Packing Coloring of Some Undirected and Oriented Coronae Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2017
%P 665-690
%V 37
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2017_37_3_a12/
%G en
%F DMGT_2017_37_3_a12
Laïche, Daouya; Bouchemakh, Isma; Sopena, Éric. Packing Coloring of Some Undirected and Oriented Coronae Graphs. Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 3, pp. 665-690. http://geodesic.mathdoc.fr/item/DMGT_2017_37_3_a12/

[1] G. Argiroffo, G. Nasini and P. Torres, Polynomial instances of the packing coloring problem, Electron. Notes Discrete Math. 37 (2011) 363–368. doi:10.1016/j.endm.2011.05.062

[2] G. Argiroffo, G. Nasini and P. Torres, The packing coloring problem for ( q, q − 4) -graphs, Lecture Notes in Comput. Sci. 7422 (2012) 309–319. doi:10.1007/978-3-642-32147-4_28

[3] G. Argiroffo, G. Nasini and P. Torres, The packing coloring problem for lobsters and partner limited graphs, Discrete Appl. Math. 164 (2014) 373–382. doi:10.1016/j.dam.2012.08.008

[4] B. Brešar, S. Klavžar and D.F. Rall, On the packing chromatic number of Cartesian products, hexagonal lattice, and trees, Discrete Appl. Math. 155 (2007) 2303–2311. doi:10.1016/j.dam.2007.06.008

[5] J. Ekstein, J. Fiala, P. Holub and B. Lidický, The packing chromatic number of the square lattice is at least 12, March 12, 2010. arXiv:1003.2291v1 [cs.DM].

[6] J. Ekstein, P. Holub and B. Lidický, Packing chromatic number of distance graphs, Discrete Appl. Math. 160 (2012) 518–524. doi:10.1016/j.dam.2011.11.022

[7] J. Ekstein, P. Holub and O. Togni, The packing coloring of distance graphs D ( k, t ), Discrete Appl. Math. 167 (2014) 100–106. doi:10.1016/j.dam.2013.10.036

[8] J. Fiala and P.A. Golovach, Complexity of the packing coloring problem for trees, Discrete Appl. Math. 158 (2010) 771–778. doi:10.1016/j.dam.2008.09.001

[9] J. Fiala, S. Klavžar and B. Lidický, The packing chromatic number of infinite product graphs, European J. Combin. 30 (2009) 1101–1113. doi:10.1016/j.ejc.2008.09.014

[10] A.S. Finbow and D.F. Rall, On the packing chromatic number of some lattices, Discrete Appl. Math. 158 (2010) 1224–1228. doi:10.1016/j.dam.2009.06.001

[11] N. Gastineau, Dichotomies properties on computational complexity of S-packing coloring problems, Discrete Math. 338 (2015) 1029–1041. doi:10.1016/j.disc.2015.01.028

[12] W. Goddard, S.M. Hedetniemi, S.T. Hedetniemi, J.M. Harris and D.F. Rall, Broadcast chromatic numbers of graphs, The 16th Cumberland Conference on Combinatorics, Graph Theory, and Computing (2003).

[13] W. Goddard, S.M. Hedetniemi, S.T. Hedetniemi, J.M. Harris and D.F. Rall, Broadcast chromatic numbers of graphs, Ars Combin. 86 (2008) 33–49.

[14] D. Korže and A. Vesel, On the packing chromatic number of square and hexagonal lattice, Ars Math. Contemp. 7 (2014) 13–22.

[15] D. Laïche, Sur les nombres broadcast chromatiques, Magister Thesis, University of Sciences and Technology Houari Boumediene, Algeria, 2010 (in French).

[16] D.F. Rall, B. Brešar, A.S. Finbow and S. Klavžar, On the packing chromatic number of trees, Cartesian products and some infinite graphs, Electron. Notes Discrete Math. 30 (2008) 57–61.

[17] C. Sloper, An eccentric coloring of trees, Australas. J. Combin. 29 (2004) 309–321.

[18] R. Soukal and P. Holub, A note on the packing chromatic number of the square lattice, Electron. J. Combin. 17 (2010).

[19] O. Togni, On packing colorings of distance graphs, Discrete Appl. Math. 167 (2014) 280–289. doi:10.1016/j.dam.2013.10.026

[20] P. Torres and M. Valencia-Pabon, The packing chromatic number of hypercubes, Discrete Appl. Math. 190–191 (2015) 127–140. doi:10.1016/j.dam.2015.04.006

[21] A. William, I. Rajasingh and S. Roy, Packing chromatic number of enhanced hypercubes, Internat. J. Math. Appl. 2 (2014) 1–6.

[22] A. William and S. Roy, Packing chromatic number of certain graphs, Internat. J. Pure Appl. Math. 87 (2013) 731–739. doi:10.12732/ijpam.v87i6.1

[23] A. William, S. Roy and I. Rajasingh, Packing chromatic number of cycle related graphs, Internat. J. Math. Soft Comput. 4 (2014) 27–33.