Search

For a graph G and a sequence S = (s1,s2,...,sk) of positive integers with s1 ≤ S2 ≤ ... ≤ Sk, we say that G is packing S-colorable or G admits a packing S-coloring, if V(G) can be partitioned into k subsets V1, V2, ..., Vk such that for each 1 ≤ i ≤ k and any x, y ∈ V, x ≠ y, there is d(x, y) ≥ Si + 1, where d(x, y) is the distance of vertices x and y in G. For simplicity, we define the packing S-coloring as packing [2, 8] coloring while S = (1, 1, 2, 2, 2, 2, 2, 2, 2, 2). In this paper, we proved that every planar graph G with maximum degree Δ ≤ 4 is packing [2,8] colorable. [ABSTRACT FROM AUTHOR]

Copyright of Palestine Journal of Mathematics is the property of Palestine Polytechnic University and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

AbstractIn 2021, we introduced one type of the generalization of dominator coloring via packing coloring and distance domination. In this paper, we present a second type of such generalization, namely distance dominator packing coloring of type II, defined as follows. A coloring c is a k-distance dominator packing coloring of type II of G if it is a k-packing coloring of G and for each u ∈ V (G) there exists i ∈ {1, 2, 3, . . . , k} such that u c(u)-distance dominates each vertex from the color class of color i (i.e., the distance between u and all vertices from color class of color i is at most c(u)). The smallest integer k such that there exists a k-distance dominator packing coloring of G is the distance dominator packing chromatic number of type II of G, denoted by . In this paper, we provide some lower and upper bounds on the distance dominator packing chromatic number of type II, characterize connected graphs G with , and consider the relation between the packing coloring, distance dominator packing coloring of type I (introduced by Ferme and Mesarič Štesl in 2021) and distance dominator packing coloring of type II for a given graph. [ABSTRACT FROM AUTHOR]

Given a non-decreasing sequence S = (s 1 , s 2 , ... , s k) of positive integers, an S -packing coloring of a graph G is a partition of the vertex set of G into k subsets { V 1 , V 2 , ... , V k } such that for each 1 ≤ i ≤ k , the distance between any two distinct vertices u and v in V i is at least s i + 1. In this paper, we study the problem of S -packing coloring of cubic Halin graphs, and we prove that every cubic Halin graph is (1 , 1 , 2 , 3) -packing colorable. In addition, we prove that such graphs are (1 , 2 , 2 , 2 , 2 , 2) -packing colorable. [ABSTRACT FROM AUTHOR]

For a graph G , the packing chromatic number of G , denoted by χ ρ (G) , is the smallest integer k such that there exists a coloring f : V (G) ↦ { 1 , ... , k } of G where every two distinct vertices u and v such that f (u) = f (v) are at pairwise distance at least f (u) + 1. In this paper, we study graphs G for which χ ρ (μ t (G)) = 2 t χ ρ (G) for all t ≥ 1 , where μ t (G) stands for the t -iterated Mycielskian of G. We show that a first natural upper bound of χ ρ (μ t (G)) is 2 t (| V (G) | − α (G) + 1) for any graph G where α (G) is the independence number of G. This bound is rounded to 2 t χ ρ (G) if the diameter of G is two. If moreover the graph G belongs to P , class of graphs whose vertex set can be partitioned into X ∪ Y such that Y is an independent set, | X | < | Y | and there is an | X | -matching M such that M = x y : x ∈ X , y ∈ Y , then χ ρ (μ t (G)) = 2 t χ ρ (G). Also, we propose a special construction of a family of maximal triangle-free graph (T n) n ≥ 5 with typical structure and show that χ ρ (μ t (T n)) = 2 t χ ρ (T n). [ABSTRACT FROM AUTHOR]

Many cutting-edge methods are now possible in real-time commercial settings and are growing in popularity on cloud platforms. By incorporating new, cutting-edge technologies to a larger extent without using more infrastructures, the information technology platform is anticipating a completely new level of development. The following concepts are proposed in this research paper: 1) A reliable authentication method Data replication that is optimised; graph-based data encryption and packing colouring in Redundant Array of Independent Disks (RAID) storage. At the data centre, data is encrypted using crypto keys called Key Streams. These keys are produced using the packing colouring method in the web graph's jump graph. In order to achieve space efficiency, the replication is carried out on optimised many servers employing packing colours. It would be thought that more connections would provide better authentication. This study provides an innovative architecture with robust security, enhanced authentication, and low cost. [ABSTRACT FROM AUTHOR]

In recent times, many innovative techniques are enabled in the real-time business environment and becoming more popular day by day in the cloud platform. The IT platform is expecting a whole new level of development by implementing new innovative technologies to a greater extent without employing additional infrastructure. Security is a critical concern in a shared environment in the current era, and it remains unresolved in the cloud. Data replication is also challenging to sustain performance, including data availability, reliability, scalability, bandwidth, access latency, and storage capacity constraints. Hence, data must be replicated to different nodes to achieve greater performance in the shared environment. Once the data is placed on to the backend storage, no proper encryption method is implemented when data is in motion and rest. This research proposes a new method to secure a one-time password in a two-factor authentication mechanism. The research employs, proves, and ensures strong security. The second method proposed in this research is to place the optimal number of replicas on different nodes to offer high availability. The replication using the packing coloring process is performed over multiple servers and optimizes the replica, which leads a path to space efficiency. The final method is a graph-based data encryption strategy that performs encryption on data in backend Redundant Array of Independent Disk (RAID) storage using crypto keys generated by the packing coloring process. The dynamic keystream considered in the proposed research offers better security. This research offers a novel architecture that proves strong security, improved authentication, and optimal replica placement with minimal cost. [ABSTRACT FROM AUTHOR]

The concept of packing coloring in graph theory is motivated by the challenge of frequency assignment in radio networks. This approach entails assigning positive integers to vertices, with the requirement that for any given label (color) i , the distance between any two vertices sharing this label must exceed i. Recently, after over 20 years of intensive research, the minimal number of colors needed for packing coloring of an infinite square grid has been established to be 15. Moreover, it is known that a hexagonal grid requires a minimum of 7 colors for packing coloring, and a triangular grid is not colorable with any finite number of colors in a packing way. Therefore, two questions come to mind: What fraction of a triangular grid can be colored in a packing model, and how much do we need to weaken the condition of packing coloring to enable coloring a triangular grid with a finite number of colors? With the partial help of the Mixed Integer Linear Programming (MILP) solver, we have proven that it is possible to color at least 72.8% but no more than 82.2% of a triangular grid in a packing way. Additionally, we have investigated the relaxation of packing coloring, called quasi-packing coloring, which is a special case of S -packing coloring. We have established that the S -packing chromatic number for the triangular grid, where S = (1 , 1 , 2 , 3 ,...) , is between 11 and 33. Furthermore, we have proven that the aforementioned sequence S is the best possible in some sense. We have also considered the partial packing and quasi-packing coloring of an infinite hypercube and present several open problems for other classes of graphs. • Triangular grid packing colorable between 72.8% and 82.2%. • Optimized S -sequence for triangular grid S -packing coloring. • Triangular grid's 2-quasi-packing chromatic number between 11 and 33. • Utilizing MILP and SAT solvers to define S -packing chromatic number bounds. • Expanding packing and quasi-packing coloring research into new graph classes. [ABSTRACT FROM AUTHOR]

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.

If S = (a1, a2, . . .) is a non-decreasing sequence of positive integers, then an S-packing coloring of a graph G is a partition of V (G) into sets X1, X2, . . . such that for each pair of distinct vertices in the set Xi, the distance between them is larger than ai. If there exists an integer k such that V (G) = X1 ∪ ∪ Xk, then the partition is called an S-packing k-coloring. The S-packing chromatic number of G is the smallest k such that G admits an S-packing k-coloring. If ai = i for every i, then the terminology reduces to packing colorings and packing chromatic number. Since the introduction of these generalizations of the chromatic number in 2008 more than fifty papers followed. Here we survey the state of the art on the packing coloring, and its generalization, the S-packing coloring. We also list several conjectures and open problems.

For 1 ≤ s 1 ≤ s 2 ≤ ... ≤ s k and a graph G , a packing (s 1 , s 2 , ... , s k) -coloring of G is a partition of V (G) into sets V 1 , V 2 , ... , V k such that, for each 1 ≤ i ≤ k the distance between any two distinct x , y ∈ V i is at least s i + 1. The packing chromatic number , χ p (G) , of a graph G is the smallest k such that G has a packing (1 , 2 , ... , k) -coloring. It is known that there are trees of maximum degree 4 and subcubic graphs G with arbitrarily large χ p (G). Recently, there was a series of papers on packing (s 1 , s 2 , ... , s k) -colorings of subcubic graphs in various classes. We show that every 2-connected subcubic outerplanar graph has a packing (1 , 1 , 2) -coloring and every subcubic outerplanar graph is packing (1 , 1 , 2 , 4) -colorable. Our results are sharp in the sense that there are 2-connected subcubic outerplanar graphs that are not packing (1 , 1 , 3) -colorable and there are subcubic outerplanar graphs that are not packing (1 , 1 , 2 , 5) -colorable. We also show subcubic outerplanar graphs that are not packing (1 , 2 , 2 , 4) -colorable and not packing (1 , 1 , 3 , 4) -colorable. [ABSTRACT FROM AUTHOR]

For a nondecreasing sequence of integers S = (s 1 , s 2 , ...) 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 s i . By setting s i = d + ⌊ i - 1 n ⌋ we obtain a (d, n)-packing coloring of a graph G. The smallest integer k for which there exists a (d, n)-packing coloring of G is called the (d, n)-packing chromatic number of G. In the special case when d and n are both equal to one we obtain the packing chromatic number of G. We determine the packing chromatic number of base-3 Sierpiński graphs and provide new results on (d, n)-packing chromatic colorings for this class of graphs. By using a dynamic algorithm, we establish the packing chromatic number for H-graphs. [ABSTRACT FROM AUTHOR]

For a non-decreasing sequence of positive integers S = (s 1 , s 2 , ...) , the S -packing chromatic number χ S (G) of G is the smallest integer k such that the vertex set of G can be partitioned into sets X i , i ∈ k ] , where vertices in X i are pairwise at distance greater than s i. In this paper we introduce S -packing chromatic vertex-critical graphs, χ S -critical for short, as the graphs in which χ S (G − u) < χ S (G) for every u ∈ V (G). This extends the earlier concept of the packing chromatic vertex-critical graphs. We show that if G is χ S -critical, then the set { χ S (G) − χ S (G − u) : u ∈ V (G) } can be almost arbitrary. If G is χ S -critical and χ S (G) = k (k ∈ N), then G is called k - χ S -critical. We characterize 3- χ S -critical graphs and partially characterize 4- χ S -critical graphs when s 1 > 1. We also deal with k - χ S -criticality of trees and caterpillars. [ABSTRACT FROM AUTHOR]

For a sequence of non-decreasing positive integers S = (s 1 , ... , s k) , a packing S -coloring is a partition of V (G) into sets V 1 , ... , V k such that for each 1 ≤ i ≤ k the distance between any two distinct x , y ∈ V i is at least s i + 1. The smallest k such that G has a packing (1 , 2 , ... , k) -coloring is called the packing chromatic number of G and is denoted by χ p (G). For a graph G , let D (G) denote the graph obtained from G by subdividing every edge. The question whether χ p (D (G)) ≤ 5 for all subcubic graphs G was first asked by Gastineau and Togni and later conjectured by Brešar, Klavžar, Rall and Wash. Gastineau and Togni observed that if one can prove every subcubic graph except the Petersen graph is packing (1 , 1 , 2 , 2) -colorable then the conjecture holds. The maximum average degree, mad(G), is defined to be max { 2 | E (H) | | V (H) | : H ⊂ G }. In this paper, we prove that subcubic graphs with m a d (G) < 30 11 are packing (1 , 1 , 2 , 2) -colorable. As a corollary, the conjecture of Brešar et al holds for every subcubic graph G with m a d (G) < 30 11 . [ABSTRACT FROM AUTHOR]

The packing chromatic number χρ(G) of a graph G is the smallest integer k such that its set of vertices V(G) can be partitioned into k disjoint subsets V1, . . . , Vk, in such a way that every two distinct vertices in Vi are at distance greater than i in G for every i, 1 ≤ i ≤ k. For a given integer p ≥ 1, the p-corona of a graph G is the graph obtained from G by adding p degree-one neighbors to every vertex of G. In this paper, we determine the packing chromatic number of p-coronae of paths and cycles for every p ≥ 1.

The packing chromatic number χp of a graph G is the smallest integer k for which there exists a mapping π: V(G) → {1, 2 ... , k} such that any two vertices of color i are at distance at least i + 1. In this paper, we give the packing chromatic number for the middle graph, total graph, central graph and line graph of helm graph and closed helm graph. [ABSTRACT FROM AUTHOR]

The packing chromatic number Xp(G) of a connected graph G is the smallest number m for which a function g:V(G) {1,2,...,m} exists, such that if g(a) = g(b) =, then d(a,b)>j. Here, we determine the packing chromatic numbers of bismuth tri-iodide and first type nanostar dendrimers. [ABSTRACT FROM AUTHOR]

Abstract A (d , n) -packing k -coloring of a graph G for integers d and n is a mapping from V (G) to the set { 1 , 2 , ... , k } such that vertices with color i ∈ { 1 , 2 , ... , k } have pairwise distance greater than d + ⌊ i − 1 n ⌋. The smallest integer k for which there exists a (d , n) -packing coloring of a graph G is called the (d , n) -packing chromatic number of G. We propose a new heuristic approach to find (d , n) -packing colorings of infinite lattices. The proposed algorithms have been able to obtain several (d , n) -packing colorings of the infinite square, hexagonal, triangular, eight-regular and octagonal lattice. The obtained results improve upper bounds on the corresponding (d , n) -packing chromatic numbers for these graphs. [ABSTRACT FROM AUTHOR]

A packing k-coloring of a graph G is a partition of V(G) into sets V1,...,Vk such that for each 1≤i≤k the distance between any two distinct x,y∈Vi is at least i+1. The packing chromatic number, χp(G), of a graph G is the minimum k such that G has a packing k-coloring. For a graph G, let D(G) denote the graph obtained from G by subdividing every edge. The questions on the value of the maximum of χp(G) and of χp(D(G)) over the class of subcubic graphs G appear in several papers. Gastineau and Togni asked whether χp(D(G))≤5 for any subcubic G, and later Brešar, Klavžar, Rall and Wash conjectured this, but no upper bound was proved. Recently the authors proved that χp(G) is not bounded in the class of subcubic graphs G. In contrast, in this paper we show that χp(D(G)) is bounded in this class, and does not exceed 8. [ABSTRACT FROM AUTHOR]

Recently, Balogh et al. (2018) answered in negative the question that was posed in several earlier papers whether the packing chromatic number is bounded in the class of graphs with maximum degree 3. In this note, we present an explicit infinite family of subcubic graphs with unbounded packing chromatic number. [ABSTRACT FROM AUTHOR]

A packing k -coloring of a graph G is a partition of V ( G ) into sets V 1 , … , V k such that for each 1 ≤ i ≤ k the distance between any two distinct x , y ∈ V i is at least i + 1 . The packing chromatic number , χ p ( G ) , of a graph G is the minimum k such that G has a packing k -coloring. Sloper showed that there are 4 -regular graphs with arbitrarily large packing chromatic number. The question whether the packing chromatic number of subcubic graphs is bounded appears in several papers. We answer this question in the negative. Moreover, we show that for every fixed k and g ≥ 2 k + 2 , almost every n -vertex cubic graph of girth at least g has the packing chromatic number greater than k . [ABSTRACT FROM AUTHOR]

Abstract: The packing chromatic number of a graph is the smallest integer such that vertices of can be partitioned into disjoint classes where vertices in have pairwise distance between them greater than . For we study the packing chromatic number of infinite distance graphs , i.e. graphs with the set of integers as vertex set and in which two distinct vertices are adjacent if and only if . We generalize results given by Ekstein et al. for graphs . For sufficiently large we prove that for both and odd, and that for exactly one of and odd. We also give some upper and lower bounds for with small and . [Copyright &y& Elsevier]

Abstract: The packing chromatic number of a graph is the smallest integer such that vertices of can be partitioned into disjoint classes where vertices in have pairwise distance greater than . We study the packing chromatic number of infinite distance graphs , i.e., graphs with the set of integers as vertex set and in which two distinct vertices are adjacent if and only if . In this paper we focus on distance graphs with . We improve some results of Togni who initiated the study. It is shown that for sufficiently large odd and for sufficiently large even . We also give a lower bound 12 for and tighten several gaps for with small . [Copyright &y& Elsevier]

Abstract: Packing coloring is a partitioning of the vertex set of a graph with the property that vertices in the -th class have pairwise distance greater than . The main result of this paper is a solution of an open problem of Goddard et al. showing that the decision whether a tree allows a packing coloring with at most classes is NP-complete. We further discuss specific cases when this problem allows an efficient algorithm. Namely, we show that it is decideable in polynomial time for graphs of bounded treewidth and diameter, and fixed parameter tractable for chordal graphs. We accompany these results by several observations on a closely related variant of the packing coloring problem, where the lower bounds on the distances between vertices inside color classes are determined by an infinite nondecreasing sequence of bounded integers. [Copyright &y& Elsevier]