Geodesic
Independence Number and Packing Coloring of Generalized Mycielski Graphs
Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 3, pp. 725-747

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

For a positive integer k ⩾ 1, a graph G with vertex set V is said to be k-packing colorable if there exists a mapping f : V ↦ 1, 2, . . ., k such that any two distinct vertices x and y with the same color f(x) = f(y) are at distance at least f(x) + 1. The packing chromatic number of a graph G, denoted by χρ(G), is the smallest integer k such that G is k-packing colorable. In this work, we study both independence and packing colorings in the m-generalized Mycielskian of a graph G, denoted μm(G). We first give an explicit formula for α (μm(G)) when m is odd and bounds when m is even. We then use these results to give exact values of α(μm(Kn)) for any m and n. Next, we give bounds on the packing chromatic number, χρ, of μm(G). We also prove the existence of large planar graphs whose packing chromatic number is 4. The rest of the paper is focused on packing chromatic numbers of the Mycielskian of paths and cycles.
Keywords: independence number, packing chromatic number, Mycielskians, generalized Mycielskians 
@article{DMGT_2021_41_3_a2,
     author = {Bidine, Ez Zobair and Gadi, Taoufiq and Kchikech, Mustapha},
     title = {Independence {Number} and {Packing} {Coloring} of {Generalized} {Mycielski} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {725--747},
     publisher = {mathdoc},
     volume = {41},
     number = {3},
     year = {2021},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2021_41_3_a2/}
}
TY  - JOUR
AU  - Bidine, Ez Zobair
AU  - Gadi, Taoufiq
AU  - Kchikech, Mustapha
TI  - Independence Number and Packing Coloring of Generalized Mycielski Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2021
SP  - 725
EP  - 747
VL  - 41
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2021_41_3_a2/
LA  - en
ID  - DMGT_2021_41_3_a2
ER  - 
%0 Journal Article
%A Bidine, Ez Zobair
%A Gadi, Taoufiq
%A Kchikech, Mustapha
%T Independence Number and Packing Coloring of Generalized Mycielski Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2021
%P 725-747
%V 41
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2021_41_3_a2/
%G en
%F DMGT_2021_41_3_a2
Bidine, Ez Zobair; Gadi, Taoufiq; Kchikech, Mustapha. Independence Number and Packing Coloring of Generalized Mycielski Graphs. Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 3, pp. 725-747. http://geodesic.mathdoc.fr/item/DMGT_2021_41_3_a2/