- Tytuł:
- Graphs that are Critical for the Packing Chromatic Number
- Autorzy:
-
Brešar, Boštjan
Ferme, Jasmina - Powiązania:
- https://bibliotekanauki.pl/articles/32318620.pdf
- Data publikacji:
- 2022-05-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
packing coloring
critical graph
diameter
block graph
tree - Opis:
- Given a graph G, a coloring c : V (G) → {1, …, k} such that c(u) = c(v) = i implies that vertices u and v are at distance greater than i, is called a packing coloring of G. The minimum number of colors in a packing coloring of G is called the packing chromatic number of G, and is denoted by χρ(G). In this paper, we propose the study of χρ-critical graphs, which are the graphs G such that for any proper subgraph H of G, χρ(H) < χρ(G). We characterize χρ-critical graphs with diameter 2, and χρ-critical block graphs with diameter 3. Furthermore, we characterize χρ-critical graphs with small packing chromatic number, and we also consider χρ-critical trees. In addition, we prove that for any graph G and every edge e ∈ E(G), we have (χρ(G)+1)/2 ≤ χρ(G−e) ≤ χρ(G), and provide a corresponding realization result, which shows that χρ(G − e) can achieve any of the integers between these bounds.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2022, 42, 2; 569-589
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł