Log in

Relevant bibliographies by topics / Graph edge-coloring / Journal articles

To see the other types of publications on this topic, follow the link: Graph edge-coloring.

Journal articles on the topic 'Graph edge-coloring'

Author: Grafiati

Published: 4 June 2021

Last updated: 6 September 2023

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the top 50 journal articles for your research on the topic 'Graph edge-coloring.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.

1

Zhong, Chuang, and Shuangliang Tian. "Neighbor Sum Distinguishing Edge (Total) Coloring of Generalized Corona Product." Journal of Physics: Conference Series 2381, no. 1 (December 1, 2022): 012031. http://dx.doi.org/10.1088/1742-6596/2381/1/012031.

Full text

Abstract:

Abstract The coloring theory of graphs is an important part of graph theory research. The key problem of the coloring theory of graphs is to determine the coloring number of each kind of coloring. Traditional coloring concepts mainly include proper vertex coloring, proper edge coloring, proper total coloring, and so on. In recent years, scholars at home and abroad have put forward some new coloring concepts, such as neighbor vertex distinguishing edge (total) coloring, and neighbor sum distinguishing edge (total) coloring, based on traditional coloring concepts and by adding other constraints. Some valuable results have been obtained, which further enrich the theory of graph coloring. For a proper [k]-edge coloring of a graph G, if for any adjacent vertex has a different sum of colors, then the coloring is a neighbor sum distinguishing [k]-edge coloring of G. For a proper [k]-total coloring of a graph G, if for any adjacent vertex has a different sum of colors, then the coloring is a neighbor sum distinguishing [k]-total coloring of G . In this paper, the coloring method and coloring index are determined by the process of induction and deduction and the construction of the dyeing method, and then the rationality of the method is verified by inverse proof and mathematical induction. If G is a simple graph with the order n ≥ 5 , and hn = (Hi ) i∈{1,2,…,n} is a sequence of disjoint simple graphs, where every Hi is a simple graph with the order m ≥ 7 . In this paper, we study the neighbor sum distinguishing edge(total) coloring of the generalized corona product G○hn of G and hn . The results are as follows: (1) If G is a path with order n , hn = (Hi ) i∈{1,2,…,n} is an alternating sequence of path and cycle with order m . If n is odd, we have χ Σ ′ ( G ∘ h n ) = m + 3 (2) If G is a path with order n , hn = (Hi ) i∈{1,2,…,n} is an alternating sequence of path and cycle with order m . If n is odd, we have χ Σ ′ ′ ( G ∘ h n ) = m + 4 Due to the late development of neighbor sum distinguishing edge (total) coloring of graphs, the related research results are relatively few. By studying the operation graph of a basic simple graph, we can provide the research basis and reference idea for the corresponding coloring of the general graph class. Therefore, it is of theoretical value to study the neighbor sum distinguishing edge (total) coloring problem of generalized corona products of graphs.

APA, Harvard, Vancouver, ISO, and other styles

2

Bagheri Gh., Behrooz, and Behnaz Omoomi. "On the simultaneous edge coloring of graphs." Discrete Mathematics, Algorithms and Applications 06, no. 04 (October 10, 2014): 1450049. http://dx.doi.org/10.1142/s1793830914500499.

Full text

Abstract:

A μ-simultaneous edge coloring of graph G is a set of μ proper edge colorings of G with a same color set such that for each vertex, the sets of colors appearing on the edges incident to that vertex are the same in each coloring and no edge receives the same color in any two colorings. The μ-simultaneous edge coloring of bipartite graphs has a close relation with μ-way Latin trades. Mahdian et al. (2000) conjectured that every bridgeless bipartite graph is 2-simultaneous edge colorable. Luo et al. (2004) showed that every bipartite graphic sequence S with all its elements greater than one, has a realization that admits a 2-simultaneous edge coloring. In this paper, the μ-simultaneous edge coloring of graphs is studied. Moreover, the properties of the extremal counterexample to the above conjecture are investigated. Also, a relation between 2-simultaneous edge coloring of a graph and a cycle double cover with certain properties is shown and using this relation, some results about 2-simultaneous edge colorable graphs are obtained.

APA, Harvard, Vancouver, ISO, and other styles

3

Sedlar, Jelena, and Riste Škrekovski. "Remarks on the Local Irregularity Conjecture." Mathematics 9, no. 24 (December 12, 2021): 3209. http://dx.doi.org/10.3390/math9243209.

Full text

Abstract:

A locally irregular graph is a graph in which the end vertices of every edge have distinct degrees. A locally irregular edge coloring of a graph G is any edge coloring of G such that each of the colors induces a locally irregular subgraph of G. A graph G is colorable if it allows a locally irregular edge coloring. The locally irregular chromatic index of a colorable graph G, denoted by χirr′(G), is the smallest number of colors used by a locally irregular edge coloring of G. The local irregularity conjecture claims that all graphs, except odd-length paths, odd-length cycles and a certain class of cacti are colorable by three colors. As the conjecture is valid for graphs with a large minimum degree and all non-colorable graphs are vertex disjoint cacti, we study rather sparse graphs. In this paper, we give a cactus graph B which contradicts this conjecture, i.e., χirr′(B)=4. Nevertheless, we show that the conjecture holds for unicyclic graphs and cacti with vertex disjoint cycles.

APA, Harvard, Vancouver, ISO, and other styles

4

Piri, Mohammad R., and Saeid Alikhani. "Introduction to dominated edge chromatic number of a graph." Opuscula Mathematica 41, no. 2 (2021): 245–57. http://dx.doi.org/10.7494/opmath.2021.41.2.245.

Full text

Abstract:

We introduce and study the dominated edge coloring of a graph. A dominated edge coloring of a graph \(G\), is a proper edge coloring of \(G\) such that each color class is dominated by at least one edge of \(G\). The minimum number of colors among all dominated edge coloring is called the dominated edge chromatic number, denoted by \(\chi_{dom}^{\prime}(G)\). We obtain some properties of \(\chi_{dom}^{\prime}(G)\) and compute it for specific graphs. Also examine the effects on \(\chi_{dom}^{\prime}(G)\), when \(G\) is modified by operations on vertex and edge of \(G\). Finally, we consider the \(k\)-subdivision of \(G\) and study the dominated edge chromatic number of these kind of graphs.

APA, Harvard, Vancouver, ISO, and other styles

5

K.S, Kanzul Fathima, and Jahir Hussain R. "An Introduction to Fuzzy Edge Coloring." JOURNAL OF ADVANCES IN MATHEMATICS 11, no. 10 (January 28, 2016): 5742–48. http://dx.doi.org/10.24297/jam.v11i10.801.

Full text

Abstract:

In this paper, a new concept of fuzzy edge coloring is introduced. The fuzzy edge coloring is an assignment of colors to edges of a fuzzy graph G. It is proper if no two strong adjacent edges of G will receive the same color. Fuzzy edge chromatic number of G is least positive integer for which G has a proper fuzzy edge coloring. In this paper, the fuzzy edge chromatic number of different classes of fuzzy graphs and the fuzzy edge chromatic number of fuzzy line graphs are found. Isochromatic fuzzy graph is also defined.

APA, Harvard, Vancouver, ISO, and other styles

6

Erzurumluoğlu, Aras, and C. A. Rodger. "On Evenly-Equitable, Balanced Edge-Colorings and Related Notions." International Journal of Combinatorics 2015 (March 4, 2015): 1–7. http://dx.doi.org/10.1155/2015/201427.

Full text

Abstract:

A graph G is said to be even if all vertices of G have even degree. Given a k-edge-coloring of a graph G, for each color i∈Zk={0,1,…,k-1} let G(i) denote the spanning subgraph of G in which the edge-set contains precisely the edges colored i. A k-edge-coloring of G is said to be an even k-edge-coloring if for each color i∈Zk, G(i) is an even graph. A k-edge-coloring of G is said to be evenly-equitable if for each color i∈Zk, G(i) is an even graph, and for each vertex v∈V(G) and for any pair of colors i,j∈Zk, |degG(i)(v)-degG(j)(v)|∈{0,2}. For any pair of vertices {v,w} let mG({v,w}) be the number of edges between v and w in G (we allow v=w, where {v,v} denotes a loop incident with v). A k-edge-coloring of G is said to be balanced if for all pairs of colors i and j and all pairs of vertices v and w (possibly v=w), |mG(i)({v,w})-mG(j)({v,w})|≤1. Hilton proved that each even graph has an evenly-equitable k-edge-coloring for each k∈N. In this paper we extend this result by finding a characterization for graphs that have an evenly-equitable, balanced k-edge-coloring for each k∈N. Correspondingly we find a characterization for even graphs to have an evenly-equitable, balanced 2-edge-coloring. Then we give an instance of how evenly-equitable, balanced edge-colorings can be used to determine if a certain fairness property of factorizations of some regular graphs is satisfied. Finally we indicate how different fairness notions on edge-colorings interact with each other.

APA, Harvard, Vancouver, ISO, and other styles

7

Furmańczyk, Hanna, Adrian Kosowski, Bernard Ries, and Paweł Żyliński. "Mixed graph edge coloring." Discrete Mathematics 309, no. 12 (June 2009): 4027–36. http://dx.doi.org/10.1016/j.disc.2008.11.033.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Adawiyah, Robiatul, Indi Izzah Makhfudloh, and Rafiantika Megahnia Prihandini. "Local edge (a, d) –antimagic coloring on sunflower, umbrella graph and its application." Alifmatika: Jurnal Pendidikan dan Pembelajaran Matematika 5, no. 1 (June 15, 2023): 70–81. http://dx.doi.org/10.35316/alifmatika.2023.v5i1.70-81.

Full text

Abstract:

Suppose a graph G = (V, E) is a simple, connected and finite graph with vertex set V(G) and an edge set E(G). The local edge antimagic coloring is a combination of local antimagic labelling and edge coloring. A mapping f∶ V (G)→ {1, 2, ..., |V (G)|} is called local edge antimagic coloring if every two incident edges e_1and e_2, then the edge weights of e_1and e_2 maynot be the same, w(e_1) ≠ w(e_2), with e = uv ∈ G, w(e) = f(u)+ f(v) with the rule that the edges e are colored according to their weights, w_e. Local edge antimagic coloring has developed into local (a,d)-antimagic coloring. Local antimagic coloring is called local (a,d)-antimagic coloring if the set of edge weights forms an arithmetic sequence with a as an initial value and d as a difference value. The graphs used in this study are sunflower graphs and umbrella graphs. This research will also discuss one of the applications of local edge (a,d)-antimagic coloring, namely the design of the Sidoarjo line batik motif. The result show that χ_le(3,1) (Sf_n) = 3n and χ_le(3n/2,1) (U_(m,n) ) = m+1 . The local (a,d)-antimagic coloring is formed into a batik motif design with characteristics from the Sidoarjo region.

APA, Harvard, Vancouver, ISO, and other styles

9

HUC, FLORIAN. "WEIGHTED-EDGE-COLORING OF k-DEGENERATE GRAPHS AND BIN-PACKING." Journal of Interconnection Networks 12, no. 01n02 (March 2011): 109–24. http://dx.doi.org/10.1142/s0219265911002861.

Full text

Abstract:

The weighted-edge-coloring problem of an edge-weighted graph whose weights are between 0 and 1, consists in finding a coloring using as few colors as possible and satisfying the following constraints: the sum of weights of edges with the same color and incident to the same vertex must be at most 1. In 1991, Chung and Ross conjectured that if G is bipartite, then [Formula: see text] colors are always sufficient to weighted-edge-color (G,w), where [Formula: see text] is the maximum of the sums of the weights of the edges incident to a vertex. We prove this is true for edge-weighted graphs with multiple edges whose underlying graph is a tree. We further generalise this conjecture to non-bipartite graphs and prove the generalised conjecture for simple edge-weighted outerplanar graphs. Finally, we introduce a list version of this coloring together with the list-bin-packing problem, which allows us to obtain new results concerning the original coloring for a specific class of graphs, namely the k-weight-degenerate weighted graph.

APA, Harvard, Vancouver, ISO, and other styles

10

Li, Minhui, Shumin Zhang, Caiyun Wang, and Chengfu Ye. "The Dominator Edge Coloring of Graphs." Mathematical Problems in Engineering 2021 (October 7, 2021): 1–7. http://dx.doi.org/10.1155/2021/8178992.

Full text

Abstract:

Let G be a simple graph. A dominator edge coloring (DE-coloring) of G is a proper edge coloring in which each edge of G is adjacent to every edge of some color class (possibly its own class). The dominator edge chromatic number (DEC-number) of G is the minimum number of color classes among all dominator edge colorings of G , denoted by χ d ′ G . In this paper, we establish the bounds of the DEC-number of a graph, present the DEC-number of special graphs, and study the relationship of the DEC-number between G and the operations of G .

APA, Harvard, Vancouver, ISO, and other styles

11

Jin, Zemin, Kun Ye, He Chen, and Yuefang Sun. "Large rainbow matchings in semi-strong edge-colorings of graphs." Discrete Mathematics, Algorithms and Applications 10, no. 02 (April 2018): 1850021. http://dx.doi.org/10.1142/s1793830918500210.

Full text

Abstract:

The lower bounds for the size of maximum rainbow matching in properly edge-colored graphs have been studied deeply during the last decades. An edge-coloring of a graph [Formula: see text] is called a strong edge-coloring if each path of length at most three is rainbow. Clearly, the strong edge-coloring is a natural generalization of the proper one. Recently, Babu et al. considered the problem in the strongly edge-colored graphs. In this paper, we introduce a semi-strong edge-coloring of graphs and consider the existence of large rainbow matchings in it.

APA, Harvard, Vancouver, ISO, and other styles

12

Cardoso, Domingos, Orestes Cerdeira, Charles Dominicc, and Pedro Cruz. "Injective edge coloring of graphs." Filomat 33, no. 19 (2019): 6411–23. http://dx.doi.org/10.2298/fil1919411c.

Full text

Abstract:

Three edges e1, e2 and e3 in a graph G are consecutive if they form a path (in this order) or a cycle of lengths three. An injective edge coloring of a graph G = (V, E) is a coloring c of the edges of G such that if e1, e2 and e3 are consecutive edges in G, then c(e1)? c(e3). The injective edge coloring number ?'i(G) is the minimum number of colors permitted in such a coloring. In this paper, exact values of ?'i(G) for several classes of graphs are obtained, upper and lower bounds for ?'i(G) are introduced and it is proven that checking whether ?'i(G) = k is NP-complete.

APA, Harvard, Vancouver, ISO, and other styles

13

M, Jagannathan, Vernold Vivin J, and Veninstine Vivik J. "Equitable Edge Coloring of Splitting Graph of Some Classes of Wheel Graphs." Ars Combinatoria 156 (July 27, 2023): 43–49. http://dx.doi.org/10.61091/ars156-05.

Full text

Abstract:

The coloring of all the edges of a graph \(G\) with the minimum number of colors, such that the adjacent edges are allotted a different color is known as the proper edge coloring. It is said to be equitable, if the number of edges in any two color classes differ by atmost one. In this paper, we obtain the equitable edge coloring of splitting graph of \(W_n\), \(DW_n\) and \(G_n\) by determining its edge chromatic number.

APA, Harvard, Vancouver, ISO, and other styles

14

Naveen, J. "Injective Edge Coloring of Cubic Graphs." Journal of Mathematical Sciences & Computational Mathematics 3, no. 1 (October 4, 2021): 26–49. http://dx.doi.org/10.15864/jmscm.3103.

Full text

Abstract:

Three edges e1, e2 and e3 in a graph G are consecutive if they form a cycle of length 3 or a path in this order. A k-injective edge-coloring of a graph G is an edge-coloring of G, (not necessarily proper), such that if edges e1, e2, e3 are consecutive, then e1 and e3 receive distinct colors. The minimum k for which G has a k-injective edge-coloring is called the injective edge-coloring number, denoted by χ′i(G). In this paper, injective edge-coloring numbers of H-graph and generalized H-graph are determined.

APA, Harvard, Vancouver, ISO, and other styles

15

Labbate, Domenico, Davide Mattiolo, Giuseppe Mazzuoccolo, Federico Romaniello, and Gloria Tabarelli. "A Characterization of Graphs with Small Palette Index." Symmetry 15, no. 1 (January 4, 2023): 154. http://dx.doi.org/10.3390/sym15010154.

Full text

Abstract:

Given an edge-coloring of a graph G, we associate to every vertex v of G the set of colors appearing on the edges incident with v. The palette index of G is defined as the minimum number of such distinct sets, taken over all possible edge-colorings of G. A graph with a small palette index admits an edge-coloring which can be locally considered to be almost symmetric, since few different sets of colors appear around its vertices. Graphs with palette index 1 are r-regular graphs admitting an r-edge-coloring, while regular graphs with palette index 2 do not exist. Here, we characterize all graphs with palette index either 2 or 3 in terms of the existence of suitable decompositions in regular subgraphs. As a corollary, we obtain a complete characterization of regular graphs with palette index 3.

APA, Harvard, Vancouver, ISO, and other styles

16

Naharwal, Lata, and Dalpat Songara. "Extended Online Graph Edge Coloring." International Journal on Computational Science & Applications 4, no. 1 (February 28, 2014): 171–78. http://dx.doi.org/10.5121/ijcsa.2014.4117.

Full text

APA, Harvard, Vancouver, ISO, and other styles

17

Cao, Yan, Guantao Chen, Guangming Jing, Michael Stiebitz, and Bjarne Toft. "Graph Edge Coloring: A Survey." Graphs and Combinatorics 35, no. 1 (January 2019): 33–66. http://dx.doi.org/10.1007/s00373-018-1986-5.

Full text

APA, Harvard, Vancouver, ISO, and other styles

18

HUC, FLORIAN, CLÁUDIA LINHARES SALES, and HERVÉ RIVANO. "THE PROPORTIONAL COLORING PROBLEM: OPTIMIZING BUFFERS IN RADIO MESH NETWORKS." Discrete Mathematics, Algorithms and Applications 04, no. 03 (August 6, 2012): 1250028. http://dx.doi.org/10.1142/s1793830912500280.

Full text

Abstract:

In this paper, we consider a new edge coloring problem to model call scheduling optimization issues in wireless mesh networks: the proportional coloring. It consists in finding a minimum cost edge coloring of a graph which preserves the proportion given by the weights associated to each of its edges. We show that deciding if a weighted graph admits a proportional coloring is pseudo-polynomial while determining its proportional chromatic index is NP-hard. We then give lower and upper bounds for this parameter that can be computed in pseudo-polynomial time. We finally identify a class of graphs and a class of weighted graphs for which the proportional chromatic index can be exactly determined.

APA, Harvard, Vancouver, ISO, and other styles

19

Huo, Jingjing, Mingchao Li, and Ying Wang. "A Characterization for the Neighbor-Distinguishing Index of Planar Graphs." Symmetry 14, no. 7 (June 21, 2022): 1289. http://dx.doi.org/10.3390/sym14071289.

Full text

Abstract:

Symmetry, such as structural symmetry, color symmetry and so on, plays an important role in graph coloring. In this paper, we use structural symmetry and color symmetry to study the characterization for the neighbor-distinguishing index of planar graphs. Let G be a simple graph with no isolated edges. The neighbor-distinguishing edge coloring of G is a proper edge coloring of G such that any two adjacent vertices admit different sets consisting of the colors of their incident edges. The neighbor-distinguishing index χa′(G) of G is the smallest number of colors in such an edge coloring of G. It was conjectured that if G is a connected graph with at least three vertices and G≠C5, then χa′(G)≤Δ+2. In this paper, we show that if G is a planar graph with maximum degree Δ≥13, then Δ≤χa′(G)≤Δ+1, and, further, χa′(G)=Δ+1 if and only if G contains two adjacent vertices of maximum degree.

APA, Harvard, Vancouver, ISO, and other styles

20

Mao, Yaping, Zhao Wang, Fengnan Yanling, and Chengfu Ye. "Monochromatic connectivity and graph products." Discrete Mathematics, Algorithms and Applications 08, no. 01 (February 26, 2016): 1650011. http://dx.doi.org/10.1142/s1793830916500117.

Full text

Abstract:

The concept of monochromatic connectivity was introduced by Caro and Yuster. A path in an edge-colored graph is called a monochromatic path if all the edges on the path are colored the same. An edge-coloring of [Formula: see text] is a monochromatic connection coloring ([Formula: see text]-coloring, for short) if there is a monochromatic path joining any two vertices in [Formula: see text]. The monochromatic connection number, denoted by [Formula: see text], is defined to be the maximum number of colors used in an [Formula: see text]-coloring of a graph [Formula: see text]. In this paper, we study the monochromatic connection number on the lexicographical, strong, Cartesian and direct products and present several upper and lower bounds for these products of graphs.

APA, Harvard, Vancouver, ISO, and other styles

21

Vikram, S. T., and S. Balaji. "An Analysis of the Factors Influencing the Strong Chromatic Index of Graphs Derived by Inflating a Few Common Classes of Graphs." Symmetry 15, no. 7 (June 23, 2023): 1301. http://dx.doi.org/10.3390/sym15071301.

Full text

Abstract:

The problem of strong edge coloring discusses assigning colors to the edges of a graph such that distinct colors are assigned to any two edges which are either adjacent to each other or are adjacent to a common edge. The least number of colors required to define a strong edge coloring of a graph is called its strong chromatic index. This problem is equivalent to the problem of assigning collision-free frequencies to the links between the elements of a wireless sensor network. In this article, we discuss a novel way of generating new graphs from existing graphs. This graph construction is known as inflating a graph. We discuss the strong chromatic index of graphs generated by inflating some common classes of graphs and graphs derived from them. In particular, we consider the cycle graph, which is symmetric in nature, and graphs such as the path graph and the star graph, which are not symmetric. Further, we analyze the factors which influence the strong chromatic index of these inflated graphs.

APA, Harvard, Vancouver, ISO, and other styles

22

Nagarathinam, R., N. Parvathi, and . "Grundy Number of Some Chordal Graphs." International Journal of Engineering & Technology 7, no. 4.10 (October 2, 2018): 64. http://dx.doi.org/10.14419/ijet.v7i4.10.20708.

Full text

Abstract:

For a given graph G and integer k, the Coloring problem is that of testing whether G has a k-coloring, that is, whether there exists a vertex mapping c : V → {1, 2, . . .} such that c(u) 12â‰ "> c(v) for every edge uv ∈ E. For proper coloring, colors assigned must be minimum, but for Grundy coloring which should be maximum. In this instance, Grundy numbers of chordal graphs like Cartesian product of two path graphs, join of the path and complete graphs and the line graph of tadpole have been executed

APA, Harvard, Vancouver, ISO, and other styles

23

Mertzios, George B., Hendrik Molter, and Viktor Zamaraev. "Sliding Window Temporal Graph Coloring." Proceedings of the AAAI Conference on Artificial Intelligence 33 (July 17, 2019): 7667–74. http://dx.doi.org/10.1609/aaai.v33i01.33017667.

Full text

Abstract:

Graph coloring is one of the most famous computational problems with applications in a wide range of areas such as planning and scheduling, resource allocation, and pattern matching. So far coloring problems are mostly studied on static graphs, which often stand in stark contrast to practice where data is inherently dynamic and subject to discrete changes over time. A temporal graph is a graph whose edges are assigned a set of integer time labels, indicating at which discrete time steps the edge is active. In this paper we present a natural temporal extension of the classical graph coloring problem. Given a temporal graph and a natural number ∆, we ask for a coloring sequence for each vertex such that (i) in every sliding time window of ∆ consecutive time steps, in which an edge is active, this edge is properly colored (i.e. its endpoints are assigned two different colors) at least once during that time window, and (ii) the total number of different colors is minimized. This sliding window temporal coloring problem abstractly captures many realistic graph coloring scenarios in which the underlying network changes over time, such as dynamically assigning communication channels to moving agents. We present a thorough investigation of the computational complexity of this temporal coloring problem. More specifically, we prove strong computational hardness results, complemented by efficient exact and approximation algorithms. Some of our algorithms are linear-time fixed-parameter tractable with respect to appropriate parameters, while others are asymptotically almost optimal under the Exponential Time Hypothesis (ETH).

APA, Harvard, Vancouver, ISO, and other styles

24

SKULRATTANAKULCHAI, SAN, and HAROLD N. GABOW. "COLORING ALGORITHMS ON SUBCUBIC GRAPHS." International Journal of Foundations of Computer Science 15, no. 01 (February 2004): 21–40. http://dx.doi.org/10.1142/s0129054104002285.

Full text

Abstract:

We present efficient algorithms for three coloring problems on subcubic graphs. (A subcubic graph has maximum degree at most three.) The first algorithm is for 4-edge coloring, or more generally, 4-list-edge coloring. Our algorithm runs in linear time, and appears to be simpler than previous ones. The second algorithm is the first randomized EREW PRAM algorithm for the same problem. It uses O(n/ log n) processors and runs in O( log n) time with high probability, where n is the number of vertices of the graph. The third algorithm is the first linear-time algorithm to 5-total-color subcubic graphs. The fourth algorithm generalizes this to get the first linear-time algorithm to 5-list-total-color subcubic graphs. Our sequential algorithms are based on a method of ordering the vertices and edges by traversing a spanning tree of a graph in a bottom-up fashion. Our parallel algorithm is based on a simple decomposition principle for subcubic graphs.

APA, Harvard, Vancouver, ISO, and other styles

25

Prajnanaswaroopa, Shantharam, Jayabalan Geetha, Kanagasabapathi Somasundaram, and Teerapong Suksumran. "Total Coloring of Some Classes of Cayley Graphs on Non-Abelian Groups." Symmetry 14, no. 10 (October 17, 2022): 2173. http://dx.doi.org/10.3390/sym14102173.

Full text

Abstract:

Total Coloring of a graph G is a type of graph coloring in which any two adjacent vertices, an edge, and its incident vertices or any two adjacent edges do not receive the same color. The minimum number of colors required for the total coloring of a graph is called the total chromatic number of the graph, denoted by χ″(G). Mehdi Behzad and Vadim Vizing simultaneously worked on the total colorings and proposed the Total Coloring Conjecture (TCC). The conjecture states that the maximum number of colors required in a total coloring is Δ(G)+2, where Δ(G) is the maximum degree of the graph G. Graphs derived from the symmetric groups are robust graph structures used in interconnection networks and distributed computing. The TCC is still open for the circulant graphs. In this paper, we derive the upper bounds for χ″(G) of some classes of Cayley graphs on non-abelian groups, typically Cayley graphs on the symmetric groups and dihedral groups. We also obtain the upper bounds of the total chromatic number of complements of Kneser graphs.

APA, Harvard, Vancouver, ISO, and other styles

26

Septory, Brian Juned, Liliek Susilowati, Dafik Dafik, and M. Venkatachalam. "On Rainbow Antimagic Coloring of Joint Product of Graphs." CAUCHY: Jurnal Matematika Murni dan Aplikasi 7, no. 4 (May 24, 2023): 548–58. http://dx.doi.org/10.18860/ca.v7i4.17471.

Full text

Abstract:

Let be a connected graph with vertex set and edge set . A bijection from to the set is a labeling of graph . The bijection is called rainbow antimagic vertex labeling if for any two edge and in path , where and . Rainbow antimagic coloring is a graph which has a rainbow antimagic labeling. Thus, every rainbow antimagic labeling induces a rainbow coloring G where the edge weight is the color of the edge . The rainbow antimagic connection number of graph is the smallest number of colors of all rainbow antimagic colorings of graph , denoted by . In this study, we studied rainbow antimagic coloring and have an exact value of rainbow antimagic connection number of joint product of graph where is graph , graph , graph , graph and graph .

APA, Harvard, Vancouver, ISO, and other styles

27

Asy’ari, M. L., Dafik, I. H. Agustin, R. Nisviasari, and R. Adawiyah. "On graceful chromatic number of some graphs." Journal of Physics: Conference Series 2157, no. 1 (January 1, 2022): 012013. http://dx.doi.org/10.1088/1742-6596/2157/1/012013.

Full text

Abstract:

Abstract We examine that all graphs in this paper are limited, simple and connected. A graceful k-coloring of a graph is a proper vertex coloring f 1 : V (G) → {1, 2,…, k} where k ≥ 2 which induces a proper edge coloring f 2 : E (G) → {1, 2,…, k − 1} characterized by f 2(uυ) = |f 1(u) — f 2 (υ)|. Nethermost k for which a graph G has a graceful k-coloring is named a graceful chromatic number of a graph G, denoted by χg (G). In our research, we will obtain the exact value of the graceful chromatic number of some graphs.

APA, Harvard, Vancouver, ISO, and other styles

28

Lestari, Dia, and I. Ketut Budayasa. "BILANGAN KETERHUBUNGAN PELANGI PADA PEWARNAAN-SISI GRAF." MATHunesa: Jurnal Ilmiah Matematika 8, no. 1 (April 23, 2020): 25–34. http://dx.doi.org/10.26740/mathunesa.v8n1.p25-34.

Full text

Abstract:

Let be a graph. An edge-coloring of is a function , where is a set of colors. Respect to a subgraph of is called a rainbow subgraph if all edges of get different colors. Graph is called rainbow connected if for every two distinct vertices of is joined by a rainbow path. The rainbow connection number of , denoted by , is the minimum number of colors needed in coloring all edges of such that is a rainbow connected. The main problem considered in this thesis is determining the rainbow connection number of graph. In this thesis, we determine the exact value of the rainbow connection number of some classes of graphs such as Cycles, Complete graph, and Tree. We also determining the lower bound and upper bound for the rainbow connection number of graph. Keywords: Rainbow Connection Number, Graph, Edge-Coloring on Graph.

APA, Harvard, Vancouver, ISO, and other styles

29

DONG, AIJUN, and GUANGHUI WANG. "NEIGHBOR SUM DISTINGUISHING COLORING OF SOME GRAPHS." Discrete Mathematics, Algorithms and Applications 04, no. 04 (December 2012): 1250047. http://dx.doi.org/10.1142/s1793830912500474.

Full text

Abstract:

A proper [k]-edge coloring of a graph G is a proper edge coloring of G using colors of the set [k] = {1, 2,…,k}. A neighbor sum distinguishing [k]-edge coloring of G is a proper [k]-edge coloring of G such that for each edge uv ∈ E(G), the sum of colors taken on the edges incident to u is different from the sum of colors taken on the edges incident to v. By ndiΣ(G), we denote the smallest value k in such a coloring of G. In this paper, we obtain that (1) ndiΣ(G) ≤ max {2Δ(G) + 1, 25} if G is a planar graph, (2) ndiΣ(G) ≤ max {2Δ(G), 19} if G is a graph such that mad(G) ≤ 5.

APA, Harvard, Vancouver, ISO, and other styles

30

Yin, Huixin, Miaomiao Han, and Murong Xu. "Strong Edge Coloring of K4(t)-Minor Free Graphs." Axioms 12, no. 6 (June 5, 2023): 556. http://dx.doi.org/10.3390/axioms12060556.

Full text

Abstract:

A strong edge coloring of a graph G is a proper coloring of edges in G such that any two edges of distance at most 2 are colored with distinct colors. The strong chromatic index χs′(G) is the smallest integer l such that G admits a strong edge coloring using l colors. A K4(t)-minor free graph is a graph that does not contain K4(t) as a contraction subgraph, where K4(t) is obtained from a K4 by subdividing edges exactly t−4 times. The paper shows that every K4(t)-minor free graph with maximum degree Δ(G) has χs′(G)≤(t−1)Δ(G) for t∈{5,6,7} which generalizes some known results on K4-minor free graphs by Batenburg, Joannis de Verclos, Kang, Pirot in 2022 and Wang, Wang, and Wang in 2018. These upper bounds are sharp.

APA, Harvard, Vancouver, ISO, and other styles

31

Sivaraman, K., and R. V. Prasad. "A STUDY ON FUZZY EQUITABLE EDGE COLORING OF WHEEL RELATED GRAPHS." Advances in Mathematics: Scientific Journal 9, no. 11 (November 3, 2020): 9311–17. http://dx.doi.org/10.37418/amsj.9.11.35.

Full text

Abstract:

Equitable edge coloring is a kind of graph labeling with the following restrictions. No two adjacent edges receive same label (color). and number of edges in any two color classes differ by at most one. In this work we are going to present the Fuzzy equitable edge coloring of some wheel related graphs.

APA, Harvard, Vancouver, ISO, and other styles

32

Ma, Hongping, Zhengke Miao, Hong Zhu, Jianhua Zhang, and Rong Luo. "Strong List Edge Coloring of Subcubic Graphs." Mathematical Problems in Engineering 2013 (2013): 1–6. http://dx.doi.org/10.1155/2013/316501.

Full text

Abstract:

We study strong list edge coloring of subcubic graphs, and we prove that every subcubic graph with maximum average degree less than 15/7, 27/11, 13/5, and 36/13 can be strongly list edge colored with six, seven, eight, and nine colors, respectively.

APA, Harvard, Vancouver, ISO, and other styles

33

McCROAN, KEITH D., and R. C. LACHER. "REGION COLORING, EDGE COLORING, AND SCAN-CONVERSION OF MAPS." International Journal of Computational Geometry & Applications 04, no. 04 (December 1994): 423–55. http://dx.doi.org/10.1142/s0218195994000239.

Full text

Abstract:

A theory is introduced relating extrinsic colorings of complementary regions of an embedded graph to certain intrinsic colorings of the edges of the graph, called color cycles, that satisfy a certain self-consistency condition. A region coloring is lifted to an edge coloring satisfying the cycle condition, and a dual construction builds a region coloring from any color cycle and any embedding of the graph. Both constructs are canonical, and the constructions are information-conservative in the sense that lifting an arbitrary region coloring to a color cycle and then reconstructing a region coloring from the cycle, using the same embedding, results in the original region coloring. The theory is motivated by, and provides the proof of correctness of, new scan-conversion algorithms that are useful in settings where region boundaries have very high complexity. These algorithms have been implemented and provide useful display functionality previously unavailable on certain rastor devices.

APA, Harvard, Vancouver, ISO, and other styles

34

Khabibah, Siti. "PEWARNAAN PADA GRAF BINTANG SIERPINSKI." Jurnal Ilmiah Matematika dan Pendidikan Matematika 9, no. 1 (June 23, 2017): 37. http://dx.doi.org/10.20884/1.jmp.2017.9.1.2853.

Full text

Abstract:

This paper discuss about Sierpinski star graph , which its construction based on the Sierpinski triangle. Vertex set of Sierpinski star graph is a set of all triangles in Sierpinski triangle; and the edge set of Sierpinski star graph is a set of all sides that are joint edges of two triangles on Sierpinski triangle. From the vertex and edge coloring of Sierpinski star graph, it is found that the chromatic number on vertex coloring of graph is 1 for n = 1 and 2 for ; while the chromatic number on edge coloring of graf is 0 for n = 1 and for

APA, Harvard, Vancouver, ISO, and other styles

35

Liu, Jia-Bao, Micheal Arockiaraj, and Antony Nelson. "Tight Bounds on 1-Harmonious Coloring of Certain Graphs." Symmetry 11, no. 7 (July 15, 2019): 917. http://dx.doi.org/10.3390/sym11070917.

Full text

Abstract:

Graph coloring is one of the most studied problems in graph theory due to its important applications in task scheduling and pattern recognition. The main aim of the problem is to assign colors to the elements of a graph such as vertices and/or edges subject to certain constraints. The 1-harmonious coloring is a kind of vertex coloring such that the color pairs of end vertices of every edge are different only for adjacent edges and the optimal constraint that the least number of colors is to be used. In this paper, we investigate the graphs in which we attain the sharp bound on 1-harmonious coloring. Our investigation consists of a collection of basic graphs like a complete graph, wheel, star, tree, fan, and interconnection networks such as a mesh-derived network, generalized honeycomb network, complete multipartite graph, butterfly, and Benes networks. We also give a systematic and elegant way of coloring for these structures.

APA, Harvard, Vancouver, ISO, and other styles

36

Wang, Yiqiao, Juan Liu, Yongtang Shi, and Weifan Wang. "Star Chromatic Index of 1-Planar Graphs." Symmetry 14, no. 6 (June 8, 2022): 1177. http://dx.doi.org/10.3390/sym14061177.

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

37

Deng, Kecai, Gexin Yu, and Xiangqian Zhou. "Recent progress on strong edge-coloring of graphs." Discrete Mathematics, Algorithms and Applications 11, no. 05 (October 2019): 1950062. http://dx.doi.org/10.1142/s1793830919500629.

Full text

Abstract:

A strong edge-coloring of a graph [Formula: see text] is a partition of its edge set [Formula: see text] into induced matchings. In this paper, we gave a short survey on recent results about strong edge-coloring of a graph.

APA, Harvard, Vancouver, ISO, and other styles

38

Vignesh, Radhakrishnan, Jayabalan Geetha, and Kanagasabapathi Somasundaram. "Total coloring conjecture for vertex, edge and neighborhood corona products of graphs." Discrete Mathematics, Algorithms and Applications 11, no. 01 (February 2019): 1950014. http://dx.doi.org/10.1142/s1793830919500149.

Full text

Abstract:

A total coloring of a graph [Formula: see text] is an assignment of colors to the elements of the graph [Formula: see text] such that no adjacent vertices and edges receive the same color. The total chromatic number of a graph [Formula: see text], denoted by [Formula: see text], is the minimum number of colors that suffice in a total coloring. Behzad and Vizing conjectured that for any simple graph [Formula: see text], [Formula: see text], where [Formula: see text] is the maximum degree of [Formula: see text]. In this paper, we prove the tight bound of the total coloring conjecture for the three types of corona products (vertex, edge and neighborhood) of graphs.

APA, Harvard, Vancouver, ISO, and other styles

39

Adawiyah, Robiatul, Muslihatul Aima, and Arika Indah Kristiana. "AN INCLUSIVE LOCAL IRREGULARITY VERTEX COLORING OF BOOK GRAPH FAMILY." BAREKENG: Jurnal Ilmu Matematika dan Terapan 17, no. 2 (June 11, 2023): 0601–8. http://dx.doi.org/10.30598/barekengvol17iss2pp0601-0608.

Full text

Abstract:

Let is a simple and connected graph with as vertex set and as edge set. Vertex labeling on inclusive local irregularity vertex coloring is defined by mapping and the function of the inclusive local irregularity vertex coloring is with . In other words, an inclusive local irregularity vertex coloring is defined by coloring the graph so that its weight value is obtained by adding up the labels of the neighboring vertex and its label. The inclusive local irregularity chromatic number is defined as the minimum number of colors obtained from coloring the vertex of the inclusive local irregularity in graph G, denoted by . In this paper, we learn about the inclusive local irregularity vertex coloring and determine the chromatic number on the book graphs.

APA, Harvard, Vancouver, ISO, and other styles

40

Hartiansyah, Fiqih, and Darmaji Darmaji. "Bilangan Kromatik Lokasi pada Graf Hasil Amalgamasi Sisi dari Graf Bintang dan Graf Lengkap." Zeta - Math Journal 8, no. 2 (July 26, 2023): 66–70. http://dx.doi.org/10.31102/zeta.2023.8.2.66-70.

Full text

Abstract:

The locating coloring of graph extends the vertex coloring dan partition dimension of graph. The minimum number of locating coloring of graph G is called the locating chromatic number of graph G. In this paper will discuss the locating chromatic number of edge amalgamation graph of star graph with order m+1 and complete graph with order n. The method used to obtain the locating chromatic number of graph is to determine the upper dan lower bound. The results obtained are that the locating chromatic number of edge amalgamation graph of star graph with order m+1 and complete graph with order n is for and .

APA, Harvard, Vancouver, ISO, and other styles

41

Gong, Zengtai, and Chen Zhang. "Adjacent Vertex Distinguishing Coloring of Fuzzy Graphs." Mathematics 11, no. 10 (May 10, 2023): 2233. http://dx.doi.org/10.3390/math11102233.

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

42

Bu, Yuehua, Qi Jia, Hongguo Zhu, and Junlei Zhu. "Acyclic edge coloring of planar graphs." AIMS Mathematics 7, no. 6 (2022): 10828–41. http://dx.doi.org/10.3934/math.2022605.

Full text

Abstract:

<abstract><p>An acyclic edge coloring of a graph $ G $ is a proper edge coloring such that no bichromatic cycles are produced. The acyclic chromatic index of $ G $, denoted by $ \chi^{'}_{a}(G) $, is the smallest integer $ k $ such that $ G $ is acyclically edge $ k $-colorable. In this paper, we consider the planar graphs without 3-cycles and intersecting 4-cycles, and prove that $ \chi^{'}_{a}(G)\leq\Delta(G)+1 $ if $ \Delta(G)\geq 8 $.</p></abstract>

APA, Harvard, Vancouver, ISO, and other styles

43

Huang, Danjun, Xiaoxiu Zhang, Weifan Wang, and Stephen Finbow. "Adjacent vertex distinguishing edge coloring of planar graphs without 3-cycles." Discrete Mathematics, Algorithms and Applications 12, no. 04 (July 14, 2020): 2050035. http://dx.doi.org/10.1142/s1793830920500354.

Full text

Abstract:

The adjacent vertex distinguishing edge coloring of a graph [Formula: see text] is a proper edge coloring of [Formula: see text] such that the color sets of any pair of adjacent vertices are distinct. The minimum number of colors required for an adjacent vertex distinguishing edge coloring of [Formula: see text] is denoted by [Formula: see text]. It is observed that [Formula: see text] when [Formula: see text] contains two adjacent vertices of degree [Formula: see text]. In this paper, we prove that if [Formula: see text] is a planar graph without 3-cycles, then [Formula: see text]. Furthermore, we characterize the adjacent vertex distinguishing chromatic index for planar graphs of [Formula: see text] and without 3-cycles. This improves a result from [D. Huang, Z. Miao and W. Wang, Adjacent vertex distinguishing indices of planar graphs without 3-cycles, Discrete Math. 338 (2015) 139–148] that established [Formula: see text] for planar graphs without 3-cycles.

APA, Harvard, Vancouver, ISO, and other styles

44

Kristiana, Arika Indah, Ahmad Aji, Edy Wihardjo, and Deddy Setiawan. "on Graceful Chromatic Number of Vertex amalgamation of Tree Graph Family." CAUCHY: Jurnal Matematika Murni dan Aplikasi 7, no. 3 (October 11, 2022): 432–44. http://dx.doi.org/10.18860/ca.v7i3.16334.

Full text

Abstract:

Proper vertex coloring c of a graph G is a graceful coloring if c is a graceful k-coloring for k∈{1,2,3,…}. Definition graceful k-coloring of a graph G=(V,E) is a proper vertex coloring c:V(G)→{1,2,…,k);k≥2, which induces a proper edge coloring c':E(G)→{1,2,…,k-1} defined c'(uv)=|c(u)-c(v)|. The minimum vertex coloring from graph G can be colored with graceful coloring called a graceful chromatic number with notation χg (G). In this paper, we will investigate the graceful chromatic number of vertex amalgamation of tree graph family with some graph is path graph, centipede graph, broom and E graph.

APA, Harvard, Vancouver, ISO, and other styles

45

Li and Yu. "New Bipartite Graph Techniques for Irregular Data Redistribution Scheduling." Algorithms 12, no. 7 (July 16, 2019): 142. http://dx.doi.org/10.3390/a12070142.

Full text

Abstract:

For many parallel and distributed systems, automatic data redistribution improves its locality and increases system performance for various computer problems and applications. In general, an array can be distributed to multiple processing systems by using regular or irregular distributions. Some data distribution adopts BLOCK, CYCLIC, or BLOCK-CYCLIC to specify data array decomposition and distribution. On the other hand, irregular distributions specify a different-size data array distribution according to user-defined commands or procedures. In this work, we propose three bipartite graph problems, including the “maximum edge coloring problem”, the “maximum degree edge coloring problem”, and the “cost-sharing maximum edge coloring problem” to formulate these kinds of distribution problems. Next, we propose an approximation algorithm with a ratio bound of two for the maximum edge coloring problem when the input graph is biplanar. Moreover, we also prove that the “cost-sharing maximum edge coloring problem” is an NP-complete problem even when the input graph is biplanar.

APA, Harvard, Vancouver, ISO, and other styles

46

Tang, Yunfeng, Huixin Yin, and Miaomiao Han. "Star edge coloring of $ K_{2, t} $-free planar graphs." AIMS Mathematics 8, no. 6 (2023): 13154–61. http://dx.doi.org/10.3934/math.2023664.

Full text

Abstract:

<abstract><p>The star chromatic index of a graph $ G $, denoted by $ \chi{'}_{st}(G) $, is the smallest number of colors required to properly color $ E(G) $ such that every connected bicolored subgraph is a path with no more than three edges. A graph is $ K_{2, t} $-free if it contains no $ K_{2, t} $ as a subgraph. This paper proves that every $ K_{2, t} $-free planar graph $ G $ satisfies $ \chi_{st}'(G)\le 1.5\Delta +20t+20 $, which is sharp up to the constant term. In particular, our result provides a common generalization of previous results on star edge coloring of outerplanar graphs by Bezegová et al.(2016) and of $ C_4 $-free planar graphs by Wang et al.(2018), as those graphs are subclasses of $ K_{2, 3} $-free planar graphs.</p></abstract>

APA, Harvard, Vancouver, ISO, and other styles

47

Joedo, J. C., Dafik, A. I. Kristiana, I. H. Agustin, and R. Nisviasari. "On the rainbow antimagic coloring of vertex amalgamation of graphs." Journal of Physics: Conference Series 2157, no. 1 (January 1, 2022): 012014. http://dx.doi.org/10.1088/1742-6596/2157/1/012014.

Full text

Abstract:

Abstract The purpose of this study is to develop rainbow antimagic coloring. This study is a combination of two notions, namely antimagic and rainbow concept. If every vertex of graph G is labeled with the antimagic labels and then edge weight of antimagic labels are used to assign a rainbow coloring. The minimum number of colors for a rainbow path to exist with the condition satisfying the edge weights w(x) ≠ w(y) for any two vertices x and y is the definition of the rainbow antimagic connection number rac(G). In this study, we use connected graphs and simple graphs in obtaining the rainbow antimagic connection number. This paper will explain the rainbow antimagic coloring on some graphs and get their formula of the rainbow antimagic connection number. We have obtained rac(G) where G is vertex amalgamation of graphs, namely path, star, broom, paw, fan, and triangular book graph.

APA, Harvard, Vancouver, ISO, and other styles

48

Prabhavathi, K., P. Jayaprakash, and M. Arockiaranjithkumar. "Effective Coloring in Fuzzy Graphs." ECS Transactions 107, no. 1 (April 24, 2022): 12035–46. http://dx.doi.org/10.1149/10701.12035ecst.

Full text

Abstract:

Coloring is the one of the important research topic in graph theory. An effective coloring is an ideal research topic in graph theory. In this paper, the coloring in fuzzy graph are investigated. In a fuzzy graph (FG), an effective coloring function is a mapping such that it is an effective edge in. In this research, the idea of an effective coloring is presented. Further investigate on effective coloring in operation of FG, like join, strong product, semi product, composition, etc.

APA, Harvard, Vancouver, ISO, and other styles

49

Chartrand, Gary, James Hallas, and Ping Zhang. "Royal Colorings of Graphs." Ars Combinatoria 156 (July 31, 2023): 51–63. http://dx.doi.org/10.61091/ars156-06.

Full text

Abstract:

For a graph \(G\) and a positive integer \(k\), a royal \(k\)-edge coloring of \(G\) is an assignment of nonempty subsets of the set \(\{1, 2, \ldots, k\}\) to the edges of \(G\) that gives rise to a proper vertex coloring in which the color assigned to each vertex \(v\) is the union of the sets of colors of the edges incident with \(v\). If the resulting vertex coloring is vertex-distinguishing, then the edge coloring is a strong royal \(k\)-coloring. The minimum positive integer \(k\) for which a graph has a strong royal \(k\)-coloring is the strong royal index of the graph. The primary emphasis here is on strong royal colorings of trees.

APA, Harvard, Vancouver, ISO, and other styles

50

Ghazaryan, Aghasi B., and Petros A. Petrosyan. "ON THE PALETTE INDEX OF GRAPHS HAVING A SPANNING STAR." Proceedings of the YSU A: Physical and Mathematical Sciences 56, no. 3 (259) (October 17, 2022): 85–96. http://dx.doi.org/10.46991/pysu:a/2022.56.3.085.

Full text

Abstract:

A proper edge coloring of a graph $G$ is a mapping $\alpha:E(G)\longrightarrow \mathbb{N}$ such that $\alpha(e)\not=\alpha(e')$ for every pair of adjacent edges $e$ and $e'$ in $G$. In a proper edge coloring of a graph $G$, the palette of a vertex $v \in V(G)$ is the set of colors assigned to the edges incident to $v$. The palette index of $G$ is the minimum number of distinct palettes occurring in $G$ among all proper edge colorings of $G$. A graph $G$ has a spanning star, if it has a spanning subgraph which is a star. In this paper, we consider the palette index of graphs having a spanning star. In particular, we give sharp upper and lower bounds on the palette index of these graphs. We also provide some upper and lower bounds on the palette index of the complete split and threshold graphs.

APA, Harvard, Vancouver, ISO, and other styles

We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!