On distance dominator packing coloring in graphs

Jasmina Ferme ; Daša Štesl

Filomat, Tome 35 (2021) no. 12, p. 4005

Résumé

Let G be a graph and let S = (s1, s2, . . . , sk) be a non-decreasing sequence of positive integers. An S-packing coloring of G is a mapping c : V(G) → {1, 2, . . . , k} with the following property: if c(u) = c(v) = i, then d(u, v) > si for any i ∈ {1, 2, . . . , k}. In particular, if S = (1, 2, 3, . . . , k), then S-packing coloring of G is well known under the name packing coloring. Next, let r be a positive integer and u, v ∈ V(G). A vertex u r-distance dominates a vertex v if dG(u, v) ≤ r. In this paper, we present a new concept of a coloring, namely distance dominator packing coloring, defined as follows. A coloring c is a distance dominator packing coloring of G if it is a packing coloring of G and for each x ∈ V(G) there exists i ∈ {1, 2, 3, . . .} such that x i-distance dominates each vertex from the color class of color i. The smallest integer k such that there exists a distance dominator packing coloring of G using k colors, is the distance dominator packing chromatic number of G, denoted by χdρ(G). In this paper, we provide some lower and upper bounds on the distance dominator packing chromatic number, characterize graphs G with χdρ(G) ∈ {2, 3}, and provide the exact values of χdρ(G) when G is a complete graph, a star, a wheel, a cycle or a path. In addition, we consider the relation between χρ(G) and χdρ(G) for a graph G

Détail

DOI : 10.2298/FIL2112005F

Classification : 05C15, 05C70, 05C12, 05C69
Keywords: Coloring, domination, S-packing coloring, packing coloring, dominator coloring, distance dominator packing coloring