- Tytuł:
- Independence Number and Packing Coloring of Generalized Mycielski Graphs
- Autorzy:
-
Bidine, Ez Zobair
Gadi, Taoufiq
Kchikech, Mustapha - Powiązania:
- https://bibliotekanauki.pl/articles/32222704.pdf
- Data publikacji:
- 2021-08-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
independence number
packing chromatic number
Mycielskians
generalized Mycielskians - Opis:
- 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.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2021, 41, 3; 725-747
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł