Search

The graphs used in this paper are simple, connected and finite graph. A graceful m -coloring of a graph G is a proper vertex coloring c : V (G) → { 1 , 2 , m } , where m ≥ 2 which induces a proper edge coloring c ′ : E (G) → { 1 , 2 , m − 1 } that defined by c ′ (u v) = | c (u) − c (v) |. Proper vertex coloring c of a graph G is a graceful coloring if c is a graceful m-coloring for m ∈ N. The minimum vertex coloring, that can apply such that a graph G can be colored with graceful coloring, is called a graceful chromatic number and it is denoted by χ g (G). In this paper, we will investigate the graceful chromatic number of generalized Petersen graph P (n , k) for k = 1 , 2 , 3 , 4. [ABSTRACT FROM AUTHOR]

Let G be a plane graph. Two edges of G are facially adjacent if they are consecutive on the boundary walk of a face of G. A facial edge coloring of G is an edge coloring such that any two facially adjacent edges receive different colors. A facial graceful k-coloring of G is a proper vertex coloring c : V (G) → {1,2,...,k} such that the induced edge coloring c' : E (G) → {1, 2,...,k -- 1} defined by c'(uv) = |c(u) -- c(v)| is a facial edge coloring. The minimum integer k for which G has a facial graceful k-coloring is denoted by Xfg(G). In this paper we prove that Xfg(G) ≤ 14 for every plane graph G and Xfg (H) ≤ 9 for every outerplane graph H. Moreover, we give exact bounds for cacti and trees. [ABSTRACT FROM AUTHOR]

Consider a simple graph G without K2 component with vertex set V and edge set E. A local antimagic labeling f of G is a one-to-one mapping of edges to distinct positive integers 1, 2, ..., |E| such that the weights of adjacent vertices are distinct, where weight of a vertex is sum of labels assigned to the edges incident to it. These weights of the vertex induced by local antimagic labeling result in a proper vertex coloring of the graph G. The local antimagic chromatic number of G, denoted as χla(G), as the smallest number of distinct weights obtained across all possible local antimagic labelings of G. In this paper, we explore the local antimagic chromatic numbers of various classes of graphs, including the union of certain graph families, the corona product of graphs, and the necklace graph. In addition, we provide constructions for infinitely many graphs for which χla(G) equals the chromatic number χ(G) of the graph. [ABSTRACT FROM AUTHOR]

The idempotent divisor graph of a commutative ring R is a graph with a vertex set in R* = R-{0}, where any distinct vertices x and y are adjacent if and only if x.y = e, for some non-unit idempotent element e^2 = e ∈ R, and is denoted by Л(R). Our goal in this work is to transform the planar idempotent divisor graph after coloring its regions into optical art by depending on the reflection of vertices, edges, and planes on the x or y-axes. That is, we achieve Op art solely through pure mathematics in this paper. [ABSTRACT FROM AUTHOR]

Lattice cryptosystem is a kind of public key cryptosystem which is resistant to quantum computing attacks. Cryptanalysis is involved in the study of lattice cryptanalysis. There are many problems such as the interdisciplinary characteristics are obvious and the research methods tend to be diversified. This paper defines new graph total colorings: graceful-difference total coloring, odd-edge graceful difference total coloring. It is proven that (1) if a connected bipartite graph G recognizes ordered graceful-difference labeling, the bipartite graph G ∗ obtained by adding m leaves to connected bipartite graph G recognizes a graceful-difference total coloring, (2) in order to establish a random coloring graphic lattice, two operations are given to design the graphic lattice. The proof of the theorem can be transformed into a feasible and effective algorithm. [ABSTRACT FROM AUTHOR]

An equitable k -coloring of a graph G is a proper vertex coloring such that | | V i | − | V j | | ≤ 1 for any i , j ∈ { 1 , 2 , ... , k } , where V i (1 ≤ i ≤ k) is the set of vertices colored with i. If there is an equitable k -coloring of G , then the graph G is said to be equitably k -colorable. In this paper, we prove that every planar graph without 5-cycles and chordal 4-cycles has an equitable k -coloring for k ≥ max { Δ (G) , 6 } , where Δ (G) is the maximum degree of  G. [ABSTRACT FROM AUTHOR]

For a graph G (V , E) and ℓ ∈ ℕ , an ℓ distance coloring is a coloring f : V → { 1 , 2 , ... , t } of V with t colors such that ∀ u , v ∈ V , u ≠ v , f (u) ≠ f (v) when d (u , v) ≤ ℓ. Here d (u , v) is the distance between u and v and is equal to the minimum number of edges that connect u and v in G. The span of ℓ distance coloring of G , χ ℓ (G) , is the minimum t among all ℓ distance coloring of G. A class of channel assignment problem in cellular network can be formulated as a distance graph coloring problem in regular grid graphs. The cellular network is often modelled as an infinite hexagonal grid H , and hence determining χ ℓ (H) has relevance from practical point of view. Jacko and Jendrol [Discussiones Mathematicae Graph Theory, 2005] determined the exact value of χ ℓ (H) for any odd ℓ and for even ℓ ≥ 8 , it is conjectured that χ ℓ (H) = 3 8 (ℓ + 4 3) 2 where [ x ] is an integer, x ∈ ℝ and x − 1 2 < [ x ] ≤ x + 1 2 . For ℓ = 8 , the conjecture has been proved by Ghosh and Koley [ 2 2 nd Italian Conference on Theoretical Computer Science, 2021]. In this paper, we prove the conjecture for any even ℓ ≥ 1 0. [ABSTRACT FROM AUTHOR]

A molecular graph p-distance coloring is a partitioning of atoms in such a way that there are no path of distance less than or equal to p between the atoms of each set. A fullerene graph is a planar 3-connected cubic graph whose faces are pentagons and hexagons. In this paper we apply some existing coloring algorithms for partitioning atoms of fullerenes based on their distances from each other. We also use these algorithm for coloring faces of some fullerenes. [ABSTRACT FROM AUTHOR]

Total coloring is a function that assigns colors to the vertices and edges of the graph such that the adjacent and the incident elements receive different colors. The minimum number of colors required for a proper total coloring of a graph G is called the total chromatic number of G and is denoted by χ ″ (G). Behzad–Vizing conjecture (Total Coloring Conjecture) states that for any graph G , χ ″ (G) ≤ Δ (G) + 2 , where Δ (G) is the maximum degree of G. In this paper, we verify the Behzad–Vizing conjecture for some product graphs. [ABSTRACT FROM AUTHOR]

Rainbow antimagic coloring is the combination of antimagic labeling and rainbow coloring. The smallest number of colors induced from all edge weights of antimagic labeling is the rainbow antimagic connection number of G , denoted by rac (G). Given a graph G with vertex set V (G) and edge set E (G) , the function f from V (G) to { 1 , 2 , ... , | V (G) | } is a bijective function. The associated weight of an edge y z ∈ E (G) under f is w (y z) = f (y) + f (z). A path R in the vertex-labeled graph G is said to be a rainbow y − z path if for any two edges y z , y ′ z ′ ∈ E (R) it satisfies w (y z) ≠ w (y ′ z ′). The function f is called a rainbow antimagic labeling of G if there exists a rainbow y − z path for every two vertices y , z ∈ V (G). When we assign each edge y z with the color of the edge weight w (y z) , we say the graph G admits a rainbow antimagic coloring. In this paper, we show the new lower bound and exact value of the rainbow antimagic connection number of comb product of any tree and complete bipartite graph. [ABSTRACT FROM AUTHOR]

An equitable coloring of a graph G is a proper vertex coloring of G such that the sizes of any two color classes differ by at most one. In the paper, we pose a conjecture that offers a gap-one bound for the smallest number of colors needed to equitably color every block graph. In other words, the difference between the upper and the lower bounds of our conjecture is at most one. Thus, in some sense, the situation is similar to that of chromatic index, where we have the classical theorem of Vizing and the Andersen–Goldberg–Seymour conjecture for multigraphs. The results obtained in the paper support our conjecture. More precisely, we verify it in the class of block graphs in which each vertex belongs to a maximum independent set. We also show that the conjecture is true for block graphs which contain a vertex that does not lie in an independent set of size larger than two. Finally, we verify the conjecture for some symmetric-like block graphs. In order to derive our results we obtain structural characterizations of block graphs from these classes. [ABSTRACT FROM AUTHOR]

An L (p1, p2, p3, ... , pm)- labeling of a graph G, has the vertices of G assigned with non-negative integers, such that the vertices at distance j should have at least pj as their label difference. If m = 3 and p1 = 3, p2 = 2, p3 = 1, it is called an L (3, 2, 1)-labeling which is widely studied in the literature. In this paper, we define an L (3, 2, 1)-path coloring of G as a labeling g : V (G) → Z+ such that between every pair of vertices there exists at least one path P where in the labeling restricted to this path is an L (3, 2, 1)-labeling. Among the labels assigned to any vertex of G under g, the maximum label is called the span of g. The L (3, 2, 1)-connection number of a graph G, denoted by k3c (G) is defined as the minimum value of span of g taken over all such labelings g. We call graphs with the special property that k3c (G) = |V (G) | as L (3, 2, 1)-path graceful. In this paper, we obtain k3c (G) of graphs that possess a Hamiltonian path and carry forward the discussion to certain classes of graphs which do not possess a Hamiltonian path, which is novel to this paper. Although different kinds of labeling are studied in the literature with different mathematical constraints imposed, the idea of showing the existence of a graph with a given number as its minimum labeling number has rarely been addressed. We show that given any positive integer, there always exists an L (3, 2, 1)-path graceful graph with the given integer as its k3c (G), thus addressing the inverse question. Finally exploiting the fact that there is no gap on the k3c (G) number line, we give an application of path colorings for secure communication on social networking sites. Efforts to deploy graph coloring in task scheduling, interference-free transmission, etc have been dealt by earlier researchers. In this paper, we deploy the L (3, 2, 1)-path coloring technique defined by us for secure communication in social networks, which has not been dealt with so far. [ABSTRACT FROM AUTHOR]

An injective k -edge coloring of a graph G is a k -edge coloring φ of G such that φ (e 1) ≠ φ (e 3) for any three consecutive edges e 1 , e 2 and e 3 of a path or a 3-cycle. The injective edge chromatic index of G , denoted by χ i ′ (G) , is the minimum k such that G has an injective k -edge coloring. Li and Chen determined the injective edge chromatic index of the generalized Petersen graph P (n , k) for 1 ≤ k ≤ 2. In this paper, we consider the injective edge coloring of the generalized Petersen graph P (c k , k) and show that χ i ′ (P (c k , k)) ≤ 5 for k ≥ 3. [ABSTRACT FROM AUTHOR]

Image coloring is a time-consuming and laborious work. For a work, color collocation is an important factor to determine its quality. Therefore, automatic image coloring is a topic with great research significance and application value. With the development of computer hardware, deep learning technology has achieved satisfactory results in the field of automatic coloring. According to the source of color information, this paper can divide automatic coloring methods into three types: image coloring based on prior knowledge, image coloring based on reference pictures, and interactive coloring. The coloring method can meet the needs of most users, but there are disadvantages such as users cannot get the multiple objects in a picture of different reference graph coloring. Aiming at this problem, based on the instance of color image segmentation and image fusion technology, the use of deep learning is proposed to implement regional mixed color more and master the method. It can be divided into foreground color based on reference picture and background color based on prior knowledge. In order to identify multiple objects and background areas in the image and fuse the final coloring results together, a method of image coloring based on CNN is proposed in this paper. Firstly, CNN is used to extract their semantic information, respectively. According to the extractive semantic information, the color of the designated area of the reference image is transferred to the designated area of the grayscale image. During the transformation, images combined with semantic information are input into CNN model to obtain the content feature map of grayscale image and the style feature map of reference image. Then, a random noise map is iterated to make the noise map approach the content feature map as a whole and the specific target region approach the designated area of the style feature map. Experimental results show that the proposed method has good effect on image coloring and has great advantages in network volume and coloring effect. [ABSTRACT FROM AUTHOR]

The concept of conflict-free connection coloring of graphs was introduced by Czap et al. in 2018. It has been the subject of several papers, which is closely related with conflict-free coloring of hypergraphs. In this survey we bring together most of the results and papers on this topic. We begin with an introduction, and then try to organize the work into three categories, conflict-free connection number, strong conflict-free connection number and conflict-free vertex-connection number. This survey also contains some conjectures, open problems and questions. [ABSTRACT FROM AUTHOR]

AbstractLet c: V(G) → {1, . . . , ℓ} = [ℓ] be a proper vertex coloring of G and C(i) = {u ∈ V(G): c(u) = i} for i ∈ [ℓ]. The k-color code rk(v|c) of vertex v is the ordered ℓ-tuple (aG(v,C(1)), . . . , aG(v,C(ℓ))) whereIf every two vertices have different color codes, then c is a (k, ℓ)-locating coloring of G. The k-locating chromatic number of graph G, denoted by , is the smallest integer ℓ such that G has a (k, ℓ)-locating coloring. In this paper, we propose this concept as an extension of diam(G)-locating chromatic number and 2-locating chromatic number which are known as the locating chromatic number, denoted χL(G), and neighbor-locating chromatic number, denoted , respectively. In this paper, we give sharp bounds for and where G◦H and are the corona and edge corona of G and H, respectively. We formulate an integer linear programming model to determine , noting that almost all graphs have diameter 2 and for every graph G of diameter 2. [ABSTRACT FROM AUTHOR]

In this paper, we study counting perfect matchings in linear chain graphs, focusing on identically colored and alternatingly colored odd faces, using recurrence relations. Our primary objective is to derive explicit formulas for the numbers of perfect matchings in linear chain graphs with identically colored odd faces. Furthermore, we establish a relationship between the numbers of perfect matchings in linear chain graphs with identically colored odd faces and strip snake chain graphs. This relationship provides us with an alternative way of validating the numbers of perfect matchings in linear chain graphs with the same colored odd faces. [ABSTRACT FROM AUTHOR]

This paper deals with the complexity of some natural graph problems parameterized by some measures that are restrictions of clique-width, such as modular-width and neighborhood diversity. We introduce a novel parameter, called iterated type partition number, that can be computed in linear time and nicely places between modular-width and neighborhood diversity. We prove that the Equitable Coloring problem is W [ 1 ] -hard when parameterized by the iterated type partition number. This result extends to modular-width, answering an open question on the complexity of Equitable Coloring when parameterized by modular-width. On the contrary, we show that the Equitable Coloring problem is FPT when parameterized by neighborhood diversity. Furthermore, we present a scheme for devising FPT algorithms parameterized by iterated type partition number, which enables us to find optimal solutions for several graph problems. As an example, in this paper, we present algorithms parameterized by the iterated type partition number of the input graph for some generalized versions of the Maximum Clique , Minimum Graph Coloring , (Total) Minimum Dominating Set , Minimum Vertex Cover and Maximum Independent Set problems. Each algorithm outputs not only the optimal value but also the optimal solution. We stress that while the considered problems are already known to be FPT with respect to modular-width, the novel algorithms are both simpler and more efficient. We finally show that the proposed scheme can be used to devise polynomial kernels, with respect to iterated type partition number, for the decisional version of most of the problems mentioned above. [ABSTRACT FROM AUTHOR]

Graph neural networks have received increased attention over the past years due to their promising ability to handle graph-structured data, which can be found in many real-world problems such as recommender systems and drug synthesis. Most existing research focuses on using graph neural networks to solve homophilous problems, and not much attention has been paid to heterophily-type problems. In this paper, we propose a graph network model for graph coloring, which is a class of representative heterophilous problems. Different from the message passing in conventional graph networks, we introduce negative message passing into a physics-inspired graph neural network for more effective information exchange in handling graph coloring problems. Moreover, a new term in the objective function taking into account the information entropy of nodes is suggested to increase the uniformity of the color assignment of each node, giving the neural network more chance to choose suitable colors for each node. Therefore, it could avoid the final solution getting stuck into the local optimum. Experimental studies are carried out to compare the proposed graph model with five state-of-the-art algorithms on ten publicly available graph coloring problems and d-regular graphs with up to 10 4 nodes, demonstrating the effectiveness of the proposed graph neural network. [ABSTRACT FROM AUTHOR]

A graph coloring is proper when the colors assigned to a pair of adjacent vertices in it are different and it is improper when at least one of the adjacent pair of vertices receives the same color. When the minimum number of colors required in a proper coloring of a graph is not available, coloring the graph with the available colors, say k colors, will lead at least an edge to have its end vertices colored with a same color. Such an edge is called a bad edge. In a proper coloring of a graph G , every color class is an independent set. However, in an improper coloring there can be few color classes that are non-independent. In this paper, we use the concept of δ (k) -coloring, which permits only one color class to be non-independent and determine the minimum number of bad edges, which is denoted by b k (G) , obtained from the same for some cycle-related graphs. [ABSTRACT FROM AUTHOR]

Graph coloring is the assignment of one color to each vertex of a graph so that two adjacent vertices are not of the same color. The graph coloring problem (GCP) is a matter of combinatorial optimization, and the goal of GCP is determining the chromatic number (G). Since GCP is an NP-hard problem, then in this paper, we propose a new approximated algorithm for finding the coloring number (it is an approximation of chromatic number) by using a graph adjacency matrix to colorize or separate a graph. To prove the correctness of the proposed algorithm, we implement it in MATLAB software, and for analysis in terms of solution and execution time, we compare our algorithm with some of the best existing algorithms that are already implemented in MATLAB software, and we present the results in tables of various graphs. Several available algorithms used the largest degree selection strategy, while our proposed algorithm uses the graph adjacency matrix to select the vertex that has the smallest degree for coloring. We provide some examples to compare the performance of our algorithm to other available methods. We make use of the Dolan-Moré performance profiles to assess the performance of the numerical algorithms, and demonstrate the efficiency of our proposed approach in comparison with some existing methods. [ABSTRACT FROM AUTHOR]

A semi-matching coloring of a finite simple graph G=(V,E) is a mapping ϕ from V to {1, ..., k} such that (i) every color class is an independent set, and (ii) the edge set of the graph induced by the union of any two consecutive color classes is a matching. A semi-matching coloring ϕ is a local coloring if, in addition, (iii) the union of any three consecutive color classes induces a triangle-free subgraph of G. In this paper, we give two counterexamples and one positive solution to three problems arisen in recent papers of You, Cao, Wang. In particular, we show that the local and semi-matching coloring problems are NP-complete on the class of split graphs. [ABSTRACT FROM AUTHOR]

In this paper, we consider equitable oriented colorings of graphs. Such coloring is a natural combination of two well‐known colorings: oriented coloring and equitable coloring. An oriented k $k$‐coloring ϕ $\phi $ of an oriented graph G→ $\overrightarrow{G}$ is an arc‐preserving homomorphism from G→ $\overrightarrow{G}$ into an oriented graph H→ $\overrightarrow{H}$ on k $k$ vertices, or colors. We say that the coloring is equitable if for every two colors c1,c2∈V(H→) ${c}_{1},{c}_{2}\in V(\overrightarrow{H})$, we have ∣∣ϕ−1(c1)∣−∣ϕ−1(c2)∣∣≤1 $| | {\phi }^{-1}({c}_{1})| -| {\phi }^{-1}({c}_{2})| | \le 1$. This paper presents the following results: we show that there is an undirected graph G $G$ such that every orientation of G $G$ is equitably oriented 5‐colorable, and we show that there is an orientation of G $G$ that cannot be colored with six colors. In other words, there is a gap in the set of numbers of colors that can be used for equitable oriented coloring of G $G$. Additionally, we concentrate on paths and show that there is an orientation of a path that requires four colors to be equitably oriented colorable. On the other hand, we show that every orientation of any path is equitably oriented k $k$‐colorable, for every k≥5 $k\ge 5$. [ABSTRACT FROM AUTHOR]

Given a graph G = (V (G) , E (G)) and a proper total k -coloring μ : V (G) ∪ E (G) → { 1 , 2 , ... , k } , we call μ neighbor sum distinguishing total coloring provided h (v) ≠ h (u) for any u v ∈ E (G) where h (v) = μ (v) + ∑ u v ∈ E (G) μ (u v) for any v ∈ V (G). Neighbor sum distinguishing total coloring was first defined by Pilśniak and Woźniak. They conjectured Δ (G) + 3 colors enable any graph G to admit such a coloring. The neighbor sum distinguishing total chromatic number χ Σ ′ ′ is the minimum integer where a graph is needed for this coloring. In this paper, we present two conclusions that χ Σ ′ ′ ≤ Δ (G) + 2 provided there are no 3-cycles adjacent to 4-cycles in a planar graph G with Δ (G) ≥ 8 without cut edges, and χ Σ ′ ′ ≤ Δ (G) + 3 provided there are no 4-cycles intersecting with 6-cycles in a planar graph G with Δ (G) ≥ 7. [ABSTRACT FROM AUTHOR]

One of the main challenges already faced by communication networks is the efficient management of increasing complexity. The recently proposed concept of cognitive networks has appeared as a candidate for addressing this issue. Cognitive networks are put forward in the framework of the evolution of network architectures as novel paradigms to provide autonomous systems in network reasoning to support end-to-end goals. This paper proposes a new method for modifying the spectral efficiency of topology control using the new vertex coloring algorithm in Thomas cognitive networks. This paper proposed a learning automatabased iterative algorithm for approximating the near-optimal solution to the vertex coloring problem in the channel control of the cognitive network. Vertex coloring is a well-known NPhard optimization problem in graph theory in which each vertex is assigned a color so that no two adjacent vertices have the same color. As the proposed algorithm proceeds, the required number of colors tends to the chromatic number of the graph since the number of channels assigned to radios will be optimal. To show the performance of the proposed algorithm, we compare it with several existing vertex coloring algorithms in terms of the number of iterations and colors required for coloring the graphs and then map this solution to the channel assignment problem. Then, we compare the results of our algorithm with other channel assignment topology control methods. The results show that the proposed algorithm is superior to the others. [ABSTRACT FROM AUTHOR]

Graph coloring is a fundamental topic in graph theory that requires an assignment of labels (or colors) to vertices or edges subject to various constraints. We focus on the harmonious coloring of a graph, which is a proper vertex coloring such that for every two distinct colors i, j at most one pair of adjacent vertices are colored with i and j. This type of coloring is edge-distinguishing and has potential applications in transportation networks, computer networks, airway network systems. The results presented in this paper fall into two categories: in the first part of the paper we are concerned with the computational aspects of finding a minimum harmonious coloring and in the second part we determine the exact value of the harmonious chromatic number for some particular graphs and classes of graphs. More precisely, in the first part we show that finding a minimum harmonious coloring for arbitrary graphs is APX-hard and that the natural greedy algorithm is a p n)-approximation. In the second part, we determine the exact value of the harmonious chromatic number for all 3-regular planar graphs of diameter 3 and some cycle-related graphs. [ABSTRACT FROM AUTHOR]

An edge coloring of a graph G results in G being rainbow connected when every pair of vertices is linked by a rainbow path. Such a path is defined as one where each edge possesses a distinct color. A rainbow coloring refers to an edge coloring that guarantees the rainbow connectedness of G. The rainbow connection number of G represents the smallest quantity of colors required to achieve rainbow connectedness under a rainbow coloring scheme. Wang and Hsu (ICICM 2019: 75–79) provided upper bounds on the size of the rainbow connection numbers in WK-recursive networks WK d , t and WK-recursive pyramids WKP d , n . In this paper, we revise their results and determine the exact values of the rainbow connection numbers of WK d , 2 for d = 3 and 4. The rainbow connection numbers of WK d , 2 are bounded between 4 and ⌊ d 2 ⌋ + 2 for d > 4 . In addition to our previous findings, we further investigate and determine upper bounds for the size of the rainbow connection numbers of WKP d , n . This involves analyzing various aspects of the graph structure and exploring potential limitations on the rainbow connection numbers. By establishing these upper bounds, we gain deeper insights into the potential range and constraints of the rainbow connection numbers within the given context. [ABSTRACT FROM AUTHOR]

Chen et al. [On coupon coloring of graphs, Discrete Appl. Math. 193 (2015) 94–101] had introduced the concept of coupon coloring for any graph with no isolated vertex. A k -coupon coloring of G is an assignment of colors from [ k ] : = { 1 , 2 , ... , k } to the vertices of G such that the neighborhood of every vertex of G contains vertices of all colors from [ k ]. The maximum k for which a k -coupon coloring exists is called the coupon coloring number of G , and is denoted by χ c (G). In this paper, we determine the coupon coloring number of Kneser graphs K (n , 2). [ABSTRACT FROM AUTHOR]

The Grundy coloring of a graph G is a proper vertex coloring in which every node colored with Ck is adjacent with all least colors of Ck. The grundy number Γ(G) is the maximum number of colors needed for proper grundy vertex coloring. In this paper, we find the accurate values of grundy chromatic number for splitting graph of cycle graph, path graph, pan graph, fan graph and double fan graph which are symbolised by Γ[S(Cn)], Γ[S(Pn)], Γ[S(n − pan)], Γ[S(F1,n)] & Γ[S(F2,n)] respectively. [ABSTRACT FROM AUTHOR]

The edge-equitable antimagic coloring has undergone comprehensive investigation across multiple graph structures, revealing that its outcomes align optimally with its equitable chromatic index. A graph, labeled using antimagic labeling, and satisfying the conditions: (i) no two adjacent edges incident on a vertex share the same edge weight, and (ii) for any distinct values i and j, the absolute difference between the cardinalities of the color classes associated with the edge weights is limited to no more than 1, is said to possess an edge-equitable antimagic coloring. This paper analyses the above coloring in specific graph families, that includes the triangular ladder graph (T Lp), open triangular ladder graph (OT Lp), comb graph (P + p ), and double comb graph (P ++ p ). [ABSTRACT FROM AUTHOR]

This paper deals with multi-factory parallel job scheduling in which independent factories try to satisfy market demand by cooperating with each other. In parallel job scheduling, unlike classical scheduling, jobs require a pre-specified job-dependent number of machines simultaneously when being processed. In the research, although it is assumed that the factories operate separately, in some cases, due to a large number of orders in one factory, some jobs may be sent to other factories to minimize the total completion time of jobs taking into account transportation time. In other words, in this system, it is assumed that each factory, after satisfying the demand of its region, can cooperate with other factories in order to achieve a better objective function for the production network. In the first step of the proposed approach, after associating the scheduling system with a constrained graph, a semidefinite programming rounding and a heuristic are proposed to color the graph in small and large-size instances, respectively. Finally, in the first step, it is shown that the problem under study can be reduced to a parallel machine scheduling problem. Given the heterogeny of factories, in the next step, mixed-integer linear programming, as well as two heuristic algorithms, are proposed. The comparison results of the proposed algorithm, imperialist competitive algorithm and the non-cooperative local scheduling algorithm show that the two-phase cooperative distributed algorithm is quite efficient. [ABSTRACT FROM AUTHOR]

A k -injective-coloring of a graph G is a mapping c : V (G) → { 1 , 2 , ⋯ , k } such that c (u) ≠ c (v) for any two vertices u and v if u and v have a common vertex. The injective chromatic number of G , denoted by χ i (G) , is the least k such that G has an injective k-coloring. In this paper, we prove that for planar graph G with g (G) ≥ 5 , Δ (G) ≥ 20 and without adjacent 5-cycles, χ i (G) ≤ Δ (G) + 2 . A -injective-coloring of a graph is a mapping such that for any two vertices and if and have a common vertex. The injective chromatic number of , denoted by , is the least such that has an injective k-coloring. In this paper, we prove that for planar graph with , and without adjacent 5-cycles, . [ABSTRACT FROM AUTHOR]

In this paper, we consider the adjacent vertex distinguishing proper edge coloring (for short, AVDPEC) and the adjacent vertex distinguishing total coloring (for short, AVDTC) of a fuzzy graph. Firstly, this paper describes the development process, the application areas, and the existing review research of fuzzy graphs and adjacent vertex distinguishing coloring of crisp graphs. Secondly, we briefly introduce the coloring theory of crisp graphs and the related theoretical basis of fuzzy graphs, and add some new classes of fuzzy graphs. Then, based on the α -cuts of fuzzy graphs and distance functions, we give two definitions of the AVDPEC of fuzzy graphs, respectively. A lower bound on the chromatic number of the AVDPEC of a fuzzy graph is obtained. With examples, we show that some results of the AVDPEC of a crisp graph do not carry over to our set up; the adjacent vertex distinguishing chromatic number of the fuzzy graph is different from the general chromatic number of a fuzzy graph. We also give a simple algorithm to construct a (d , f) -extended AVDPEC for fuzzy graphs. After that, in a similar way, two definitions of the AVDTC of fuzzy graphs are discussed. Finally, the future research directions of distinguishing coloring of fuzzy graphs are given. [ABSTRACT FROM AUTHOR]

Let G be a simple graph and χ′(G) be the chromatic index of G. We call G a Δ‐critical graph if χ′(G − e ) = χ′( ) G − 1 = Δ for every edge e of G, where Δ is maximum degree of G. Let e x = y be an edge of Δ‐critical graph G and φ be an (proper) edge Δ‐coloring of G − e . An e‐fan is a sequence F x, e, y, e1, z1, ..., ep, zp of alternating vertices and distinct edges such that edge ei is incident with x or y, zi is another endvertex of ei and φ(ei ) is missing at a vertex before zi for each i with 1 ≤ i ≤ p. In this paper, we prove that if min, { ( dx) d(y)} ≤ Δ − 1, where d (x) and d ( y ) denote the degrees of vertices x and y, respectively, then colors missing at different vertices of V ( Fe ) are distinct. Clearly, a Vizing fan is an e‐fan with the restricting that all edges ei being incident with one fixed end vertex of edge e. This result gives a common generalization of several recently developed new results on multifan, double fan, Kierstead path of four vertices, and broom. By treating some colors of edges incident with vertices of low degrees as missing colors, Kostochka and Stiebitz introduced C‐fan. In this paper, we also generalize the C‐fan from centered at one vertex to one edge. [ABSTRACT FROM AUTHOR]

An α , β -Kempe swap in a properly colored graph interchanges the colors on some component of the subgraph induced by colors α and β . Two k-colorings of a graph are k-Kempe equivalent if we can form one from the other by a sequence of Kempe swaps (never using more than k colors). Las Vergnas and Meyniel showed that if a graph is (k - 1) -degenerate, then each pair of its k-colorings are k-Kempe equivalent. Mohar conjectured the same conclusion for connected k-regular graphs. This was proved for k = 3 by Feghali, Johnson, and Paulusma (with a single exception K 2 □ K 3 , also called the 3-prism) and for k ≥ 4 by Bonamy, Bousquet, Feghali, and Johnson. In this paper we prove an analogous result for list-coloring. For a list-assignment L and an L-coloring φ , a Kempe swap is called L-valid for φ if performing the Kempe swap yields another L-coloring. Two L-colorings are called L-equivalent if we can form one from the other by a sequence of L-valid Kempe swaps. Let G be a connected k-regular graph with k ≥ 3 and G ≠ K k + 1 . We prove that if L is a k-assignment, then all L-colorings are L-equivalent (again excluding only K 2 □ K 3 ). Further, if G ∈ { K k + 1 , K 2 □ K 3 } , L is a Δ -assignment, but L is not identical everywhere, then all L-colorings of G are L-equivalent. When k ≥ 4 , the proof is completely self-contained, implying an alternate proof of the result of Bonamy et al. Our proofs rely on the following key lemma, which may be of independent interest. Let H be a graph such that for every degree-assignment L H all L H -colorings are L H -equivalent. If G is a connected graph that contains H as an induced subgraph, then for every degree-assignment L G for G all L G -colorings are L G -equivalent. [ABSTRACT FROM AUTHOR]

In this paper we identify the causes of numerical non-reproducibility in the unstructured mesh computational motif, a class of algorithms commonly used for the solution of PDEs. We introduce a number of parallel and distributed algorithms to address nondeterminism in the order of floating-point computations, in particular, a new graph coloring scheme that produces identical coloring results regardless of how many parts the graph is partitioned to. We implement these in the OP2 domain specific language (DSL) and show how it can be automatically deployed to any application that uses OP2 without user intervention. We contrast differences in results without reproducibility and then demonstrate how bitwise reproducibility can be gained using our methods on a variety of applications including a production CFD application used at Rolls-Royce. We evaluate the performance and overheads of enforcing bitwise reproducibility on a cluster of CPUs and GPUs. [ABSTRACT FROM AUTHOR]

A tree T on 2n vertices is called set-sequential if the elements in V (T) ∪ E(T) can be labeled with distinct nonzero (n + 1)-dimensional 01-vectors such that the vector labeling each edge is the component-wise sum modulo 2 of the labels of the endpoints. It has been conjectured that all trees on 2n vertices with only odd degree are set-sequential (the "Odd Tree Conjecture"), and in this paper, we present progress toward that conjecture. We show that certain kinds of caterpillars (with restrictions on the degrees of the vertices, but no restrictions on the diameter) are set-sequential. Additionally, we introduce some constructions of new set-sequential graphs from smaller set-sequential bipartite graphs (not necessarily odd trees). We also make a conjecture about pairings of the elements of Fn2 in a particular way; in the process, we provide a substantial clarification of a proof of a theorem that partitions Fn2 from a paper [P.N. Balister, E. Győri and R.H. Schelp, Coloring vertices and edges of a graph by nonempty subsets of a set, European J. Combin. 32 (2011) 533-537]. Finally, we put forward a result on bipartite graphs that is a modification of a theorem in the aforementioned paper. [ABSTRACT FROM AUTHOR]

The Alon–Tarsi number was defined by Jensen and Toft (Graph coloring problems, Wiley, New York, 1995). The Alon–Tarsi number AT(G) of a graph G is the smallest integer k such that G has an orientation D with maximum outdegree k - 1 and the number of even circulation is not equal to that of odd circulations in D. It is known that χ (G) ≤ χ l (G) ≤ A T (G) for any graph G, where χ (G) and χ l (G) are the chromatic number and the list chromatic number of G. Denote by H 1 □ H 2 and H 1 ⋈ H 2 the Cartesian product and the semi-strong product of two graphs H 1 and H 2 , respectively. Kaul and Mudrock (Electron J Combin 26(1):P1.3, 2019) proved that A T (C 2 k + 1 □ P n) = 3 . Li, Shao, Petrov and Gordeev (Eur J Combin 103697, 2023) proved that A T (C n □ C 2 k) = 3 and A T (C 2 m + 1 □ C 2 n + 1) = 4 . Petrov and Gordeev (Mosc. J. Comb. Number Theory 10(4):271–279, 2022) proved that A T (K n □ C 2 k) = n . Note that the semi-strong product is noncommutative. In this paper, we determine A T (P m ⋈ P n) , A T (C m ⋈ C 2 n) , A T (C m ⋈ P n) and A T (P m ⋈ C n) . We also prove that 5 ≤ A T (C m ⋈ C 2 n + 1) ≤ 6 . [ABSTRACT FROM AUTHOR]

An edge-locating coloring of a simple connected graph G is a partition of its edge set into matchings such that the vertices of G are distinguished by the distance to the matchings. The minimum number of the matchings of G that admits an edge-locating coloring is the edge-locating chromatic number of G, and denoted by χ'L(G). This paper introduces and studies the concept of edgelocating coloring. Graphs G with χ'L(G) ∈ {2, m} are characterized, where m is the size of G. We investigate the relationship between order, diameter and edge-locating chromatic number. We obtain the exact values of χ'L(Kn) and χ'L(Kn - M), where M is a maximum matching; indeed this result is also extended for any graph. We determine the edge-locating chromatic number of the join graphs of some well-known graphs. In particular, for any graph G, we show a relationship between χ'L(G + K1) and ∆(G). We investigate the edge-locating chromatic number of trees and present a characterization bound for any tree in terms of maximum degree, number of leaves, and the support vertices of trees. Finally, we prove that any edge-locating coloring of a graph is an edge distinguishing coloring. [ABSTRACT FROM AUTHOR]

If G is a connected finite simple graph with its vertices properly colored with k colors appearing, then with respect to an ordering of the colors, to each vertex v a k-tuple can be assigned whose entries give the distances in G from v to the different color sets. The locating chromatic number (lcn) of G is the smallest k for which a proper vertex coloring of G with k colors appearing exists such that the corresponding k-tuples are distinct. In this paper we obtain by construction upper bounds on the lcns of shadow cycle graphs. [ABSTRACT FROM AUTHOR]

A vertex coloring of a graph G is called acyclic if no two adjacent vertices have the same color and no cycle in G is bichromatic. The acyclic chromatic number a(G) of a graph G is the least number of colors in an acyclic coloring of G. In this paper, we obtain bound for the acyclic chromatic number of the strong product of a tree and a graph. An exact value for the acyclic chromatic number of the strong product of two trees is derived. Further observations are made on the upper bound for the strong product of three paths. [ABSTRACT FROM AUTHOR]

An edge labeling of a connected graph G = (V, E) is said to be local antimagic if it is a bijection f : E → {1,..., |E|} such that for any pair of adjacent vertices x and y, f+(x) ≠ f+(y), where the induced vertex label f+(x) = Σ f (e), with e ranging over all the edges incident to x. The local antimagic chromatic number of G, denoted by Xla(G), is the minimum number of distinct induced vertex labels over all local antimagic labelings of G. In this paper, the sharp lower bound of the local antimagic chromatic number of a graph with cut-vertices given by pendants is obtained. The exact value of the local antimagic chromatic number of many families of graphs with cut-vertices (possibly given by pendant edges) are also determined. Consequently, we partially answered Problem 3.1 in [Local antimagic vertex coloring of a graph, Graphs and Cow,bin., 33, (2017), 275-285]. [ABSTRACT FROM AUTHOR]

A dominator coloring of a graph G is a proper vertex coloring with a domination property that each vertex dominates a color class. The minimum number of colors used in a dominator coloring of G is called dominator chromatic number of G and is denoted as χ d (G). Graphs with χ d (G) ≤ 3 have characterizations and such graphs can be recognized in polynomial time. However, for k ≥ 4 , deciding whether χ d (G) ≤ k is NP-hard. In this paper, we investigate the computational complexity of minimum q -dominator partization problem (Min- q -D-Partz). In Min- q -D-Partz, given a graph G , the objective is to find a vertex set S of minimum size such that χ d (G [ V ∖ S ]) ≤ q. We prove that Min- 2 -D-Partz is APX-complete and has a two-factor approximation algorithm. We also prove that Min- 3 -D-Partz cannot be approximated within any constant factor and can be approximated within a factor of O (log n). [ABSTRACT FROM AUTHOR]