Search

The strong edge-coloring of a graph G is a proper edge coloring such that all edges adjacent to any given edge receive different colors. Such an assignment of colors defines color classes all of which are induced matchings. The minimum number of color classes required for such an assignment of colors is defined as the strong chromatic index of a graph G. In this article, we discuss the strong chromatic index of graphs obtained by the amalgamation of two graphs, the rooted product of two graphs and the corona product of two graphs. [ABSTRACT FROM AUTHOR]

Let be a simple connected graph consisting of n vertices and m edges. In a proper l -coloring, an r -dynamic coloring of a graph is one in which each vertex's neighbors are provided at least min { r , d (k) } different colors. The r -dynamic chromatic number of graph , given as χ r () , is the minimal l such that the graph has r -dynamic l coloring of . In this study, we combine a few common graphs to provide the r -dynamic coloring of the subdivision-edge neighborhood corona of path graph P s and star graph K 1 , s . These graphs include path graph P q , cycle graph C q , complete graph K q , star graph K 1 , q , and double star graph K 1 , q , q . [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]

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]

A proper vertex coloring of a graph G is equitable if the sizes of any two color classes differ by at most one. The equitable chromatic number of a graph G , denoted by χ = (G) , is the minimum k such that G is equitably k -colorable. In this paper, we discuss some basic properties of equitable critical graphs as well as equitable k -critical graphs. A graph G is called equitable critical if χ = (H) ≠ χ = (G) for every proper subgraph H of G. G is called equitable k -critical if it is equitable k -chromatic and equitable critical. Furthermore, we discuss that equitable vertex (edge) critical, equitable critical vertex (edge) graphs. [ABSTRACT FROM AUTHOR]

Let G be a simple graph and connected. A function l : V (G) → { 1 , 2 , ... , k } is called vertex irregular k -labeling and w : V (G) → N where w (u) = ∑ v ∈ N (u) l (v). The function of f is called local irregular vertex coloring if every u v ∈ E (G) , w (u) ≠ w (v) and opt (l) = min { max l i ; l i vertex irregular labeling}. The local irregular chromatic number is denoted by χ lis (G). In this paper, we study local irregular vertex coloring of S m ▹ v 0 S n , S m ▹ v 1 S n , and S m ▹ v 1 P n. [ABSTRACT FROM AUTHOR]

For a graph G = (V , E) , an edge connectivity λ is the minimum number of edges whose removal disconnects G. In this paper, we define property restricted edge connectivity. Then we appraise its particular case, more precisely k-restricted edge connectivity. Some of the basic properties of k-restricted edge connectivity are considered. We also discuss how k-restricted edge connectivity associates with graph coloring. In particular, we try to study how k-restricted edge connectivity relates with Tait's coloring theorem and thereby the famous Four-color conjecture. [ABSTRACT FROM AUTHOR]

The k-2-distance coloring of graph G is a mapping c : V (G) → { 1 , 2 , ... , k } if any two vertices at distance at most two from each other get different colors. The 2-distance chromatic number is the smallest integer k such that G has a k-2-distance coloring, denoted by χ 2 (G). In this paper, we prove that every planar graph G without 3-cycles and intersecting 4-cycles and Δ (G) ≥ 8 1 has χ 2 (G) ≤ Δ + 5. [ABSTRACT FROM AUTHOR]

A total dominator coloring of a graph G is a proper coloring of G in which each vertex of the graph is adjacent to every vertex of some color class. The total dominator chromatic number of a graph is the minimum number of color classes in a total dominator coloring. In this paper, we study the total dominator coloring on middle graphs by giving several bounds for the case of general graphs and trees. Moreover, we calculate explicitly the total dominator chromatic number of the middle graph of several known families of graphs. [ABSTRACT FROM AUTHOR]

Indicated coloring is a graph coloring game in which two players collectively color the vertices of a graph in the following way. In each round, the first player (Ann) selects a vertex, and then the second player (Ben) colors it properly, using a fixed set of colors. The goal of Ann is to achieve a proper coloring of the whole graph, while Ben is trying to prevent the realization of this project. The smallest number of colors necessary for Ann to win the game on a graph G (regardless of Ben's strategy) is called the indicated chromatic number of G, denoted by χ i (G). In this paper, we examine whether the Mycielskian of G, μ (G) , is k-indicated colorable for all k ≥ χ i (μ (G)) , whenever G is l-indicated colorable for all l ≥ χ i (G). In this direction, we prove that the Mycielskian of the bipartite graphs, complete multipartite graphs, { P 5 , K 3 } -free graphs, { P 5 , K 4 , K i t e , B u l l } -free graphs, { 2 K 2 , C 4 } -free graphs and { P 6 , C 5 , P 5 ¯ , K 1 , 3 } -free graphs are k-indicated colorable for all k greater than or equal to the indicated chromatic number of the corresponding graphs. [ABSTRACT FROM AUTHOR]

We propose a modification of the First-Fit algorithm in which we forbid the use of the most frequently used color. We provide some lower bound of the performance ratio χ FF w P (G) ω (G) on the family of interval graphs G , where χ FF w P (G) denotes the number of used colors by the modified version of the First-Fit algorithm and ω (G) is the number of vertices in the largest complete subgraph in G. We also compare the modification with the usual First-Fit algorithm on some experimental data. [ABSTRACT FROM AUTHOR]

Let G = (V , E) be a simple, finite, undirected, and connected graph with vertex set V (G) and edge set E (G). A bijection l : V (G) → { 1 , 2 , ... , k } is label function l if opt (l) = min { max (l i) : l i   v e r t e x   i r r e g u l a r   l a b e l i n g } and for any two adjacent vertices u and v , w (u) ≠ w (v) where w (u) = ∑ v ∈ N (u) l (v) and N (u) is set of vertices adjacent to v. w is called local irregularity vertex coloring. The minimum cardinality of local irregularity vertex coloring of G is called chromatic number local irregular denoted by χ l i s (G). In this paper, we verify the exact values of volcano, broom, parachute, double broom and complete multipartite graphs. [ABSTRACT FROM AUTHOR]

Many symmetric properties are well-explored in graph theory, especially in graph coloring, such as symmetric graphs defined by the automorphism groups, symmetric drawing of planar graphs, and symmetric functions which are used to count the number of specific colorings of a graph. This paper is devoted to studying the star edge coloring of 1-planar graphs. The star chromatic index χ st ′ (G) of a graph G is defined as the smallest k for which the edges of G can be colored by using k colors so that no two adjacent edges get the same color and no bichromatic paths or cycles of length four are produced. A graph G is called 1-planar if it can be drawn in the plane such that each edge crosses at most one other edge. In this paper, we prove that every 1-planar graph G satisfies χ st ′ (G) ≤ 7.75 Δ + 166 ; and moreover χ st ′ (G) ≤ ⌊ 1.5 Δ ⌋ + 500 if G contains no 4-cycles, and χ st ′ (G) ≤ 2.75 Δ + 116 if G is 3-connected, or optimal, or NIC-planar. [ABSTRACT FROM AUTHOR]

The strong chromatic index χ s ′ (G) of a graph G is the minimum number of colors needed in a proper edge-coloring so that every color class induces a matching in G. It was proved In 2013, that every outerplanar graph G with Δ ≥ 3 has χ s ′ (G) ≤ 3 Δ − 3 . In this paper, we give a characterization for an outerplanar graph G to have χ s ′ (G) = 3 Δ − 3 . We also show that if G is a bipartite outerplanar graph, then χ s ′ (G) ≤ 2 Δ ; and χ s ′ (G) = 2 Δ if and only if G contains a particular subgraph. [ABSTRACT FROM AUTHOR]

An acyclic edge coloring of a graph G is a proper edge coloring such that no bichromatic cycles are produced. It was conjectured that every simple graph G with maximum degree Δ is acyclically edge- (Δ + 2) -colorable. In this paper, we confirm the conjecture for chordal graphs G with Δ ≤ 6 . [ABSTRACT FROM AUTHOR]