- Tytuł:
- The s-packing chromatic number of a graph
- Autorzy:
-
Goddard, Wayne
Xu, Honghai - Powiązania:
- https://bibliotekanauki.pl/articles/743305.pdf
- Data publikacji:
- 2012
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
graph
coloring
packing
broadcast chromatic number - Opis:
- Let S = (a₁, a₂, ...) be an infinite nondecreasing sequence of positive integers. An S-packing k-coloring of a graph G is a mapping from V(G) to {1,2,...,k} such that vertices with color i have pairwise distance greater than $a_i$, and the S-packing chromatic number $χ_S(G)$ of G is the smallest integer k such that G has an S-packing k-coloring. This concept generalizes the concept of proper coloring (when S = (1,1,1,...)) and broadcast coloring (when S = (1,2,3,4,...)). In this paper, we consider bounds on the parameter and its relationship with other parameters. We characterize the graphs with $χ_S = 2$ and determine $χ_S$ for several common families of graphs. We examine $χ_S$ for the infinite path and give some exact values and asymptotic bounds. Finally we consider complexity questions, especially about recognizing graphs with $χ_S = 3$.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2012, 32, 4; 795-806
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł