Search

The focus of the presented article is put on the analysis of edge coloring of selected sets of graphs - we are specifically interested in edge 3-coloring of graphs called snarks. Previous research suggests, that while using a single coloring algorithm and using various initial graph coloring edges, coloring of such graph may take anywhere from time lower than one millisecond to the time ranging in hundreds of milliseconds. In our case, we use recursive backtracking coloring algorithm based on breadth-first search and implement the change of initial graph coloring edge via permutation of adjacency matrix of graph. In this article, we present a tool created for the needs of analysis of edge coloring of graphs which is based on visualization of edge coloring and we present several problematic subgraphs and patterns which increase the time of edge coloring of cubic graphs.

Based on the graph generation algorithm, we propose a novel algorithm to solve the problem of D(β)-vertices sum distinguishing edge coloring of some kinds of special graphs. Our main contributions to solving this graph coloring problem are: firstly, we generate the adjacent matrices of the following graphs; secondly, we input these matrices to our designed algorithm; thirdly, the algorithm will output the corresponding D(β)-vertices sum distinguishing edge coloring matrices; fourthly, through analyzing of the results obtained by our algorithm, we conclude that regular chromatic number are found in some of the graphs involved. We think that our proposed algorithm is innovative and can be adopted by other researchers.

In this paper, an adjacent vertex sum reducible edge coloring algorithm (AVSREC) is designed, which can be applied to graphic cryptography. Through the user testing experiment of the identity authentication prototype system, it is verified that the graph password based on the adjacent vertex sum reducible edge coloring algorithm can better prevent shoulder peeping attack and improve the security effectively, and its usability is better than text password and general graphic password.

Vertex distinguishing total coloring of graph $G=(p, q)$ refers to the coloring of vertices and edges, so that any vertex coloring is different, adjacent edge coloring is different, vertex and its associated edge coloring are different, the coloring of vertex and its associated edge is different, and any two points $u, v$ that are different from each other in $G$ have $C(U)\neq C(V)$ , where $C(x)$ represents the set of colors of vertex $x$ and edge associated with $x$ under $f$ . Then $f$ is called vertex distinguishing total coloring of graph $G$ , which is called $VDTC$ coloring for short. We call $\psi_{vdtc}(G) =\min$ { $k\vert$ there exists a $k-VDTC$ of $G$ }, and call $\psi_{vdtc}(G)$ the vertex distinguishing total chromatic number of $G$ . In this paper, we design an accurate algorithm for $K_{n}-E(K_{2,m})(n\geq 3,m\geq 2)$ graphs. By using this algorithm, we can get the vertex distinguishing total coloring of $K_{n}-E(K_{2,m})$ graphs within finite vertexs. Through the analysis of the results, some theorems are summarized and proved, and further conjectures are given.

In graph theory, graph colorings are a major area of study. Graph colorings involve the constrained assignment of labels (colors) to vertices or edges. There are many types of colorings defined in the literature, the most common being the proper vertex coloring. The proper vertex $k$ -coloring is defined as a vertex coloring from a set of $k$ colors such that no two adjacent vertices have the same color. In this paper, we focus on a variant of the proper vertex $k$ -coloring problem, termed graceful coloring. A graceful $k$ -coloring of an undirected connected graph $G$ is a proper vertex coloring using $k$ colors, that induces a proper edge coloring, where the color for an edge ( $u, v$ ) is the absolute value of the difference between the colors assigned to vertices $u$ and $v$ . The minimum $k$ for which a graph $G$ has a graceful $k$ -coloring is termed the graceful chromatic number of the graph. In a previous work (Mincu, Obreja, Popa, SYNASC 2019) we find the graceful chromatic number for some well-known graphs and classes of graphs, such as diamond graph, Petersen graph, Moser spindle graph, Goldner-Harary graph, friendship graphs, fan graphs, and others. In this study, we continue the investigation and find the graceful chromatic number for other well-known individual graphs, like Durer graph, Heawood graph, Mobius-Kantor graph, Nauru graph, Tietze's graph, Golomb graph and classes of graphs, like cactus, Gear, web graphs, etc. In a previous work (Mincu, Obreja, Popa, SYNASC 2019) we find the graceful chromatic number for some well-known graphs and classes of graphs, such as diamond graph, Petersen graph, Moser spindle graph, Goldner-Harary graph, friendship graphs, fan graphs, and others. In this study, we continue the investigation and find the graceful chromatic number for other well-known individual graphs, like Durer graph, Heawood graph, Mobius-Kantor graph, Nauru graph, Tietze's graph, Golomb graph and classes of graphs, like cactus, Gear, web graphs, etc.

A new algorithm for vertex-distinguishing edge coloring of graph is designed. First of all, by definition of vertex-distinguishing edge coloring, we know that there exist two constraints rules, one is the edge constraint and the other is the vertex color set constraint. Second, we established objective function according to the two constraint rules. Third, based on the exchange rules, an algorithm is designed to make the objective function meet the requirements. The algorithm steps are described in detail. The experimental results show that the vertex-distinguishing edge coloring obtained by the algorithm conforms to the coloring conditions. This algorithm can effectively solve this coloring problem of graphs with large number of vertices.

In this paper, we derive two theorems of vertex-distinguishing equitable edge coloring of product graph by using constructive method, and present the vertex-distinguishing equitable edge chromatic numbers, which the rquired minimum number of colors is called the vertex-Distinguishing equitable edge chromatic number of product graphs between complete graph and complete graph, star and star, wheel and wheel, which verify the conjecture on VDEECC.

This paper presents solution to problem of edge coloring of sizable set of cubic graphs and examination of relations between these graphs. We solved this problem on various computing systems and for various sizes of the problem (various number of graphs). For the computations we used High-Performance Computing Cluster and Amazon Web Services cloud environment. We measured and analyzed time of computation of edge coloring and other properties. Largest set we worked with contained almost 10 million graphs. We created new methodology, which can be used to finding order of the edges which optimizes time of computation of edge coloring for certain subset of graphs. On the basis of this methodology, we implemented algorithm for parallel edge coloring of set of graphs. For testing of the methodology, we designed 8 experiments. Results showed, that worst time of edge coloring of graph from set of 19 935 graphs before use of the methodology was 1260 ms. After application of our methodology, we found same order of edge coloring for whole group of 19 935 graphs and the highest time of coloring was 10 ms.

one of the most common issues at a school is the Course Timetabling Problem (CTP) generating. A vast number of students are enrolling in multiple classes every semester. The time concern, subjects, classrooms for both teaching staff and students make it challenging to present a perfect schedule in a limit period. Using graph knowledge is one way of solving this issue. The CTP is an NP-hard problem. It grows difficulties to complete graph levels with strict constraints. In this research, we chose the Edge coloring methodology and implemented it by utilizing the Jedit programming language tool to solve this issue. Jedit, which is a course teaching programming language, used to color a bipartite graph and outcome a scheduled course timetable. It has many available methods that are easy to implement and use in our solution. Also, we participated by adding a new method to Jedit’s collections. As a result, we found that a maximum coloring (k) of an indirect bipartite graph (G) would depend on the maximum edges (E) that are sharing a vertex (N) from the same set in (G), such that (two adjacent edges would be colored with a different color). Additionally, the nodes in each set would color similarly. Finally, it cleared that Δk equals ΔE., So we concluded that Jedit is a suitable and easy new way to solve the problematic scheduling issue and provided efficient results using the proposed method.

The traffic of large-scale interconnection networks is increasingly showing high-speed and high-burst characteristics, which imposes a big challenge on the performance of switching systems. However, the existing scheduling and routing algorithms for the switching systems have either high computation complexity or high operation cost, which cannot keep up with the rapid development of the Internet. To cope with this problem, we present a parallel scheduling algorithm and a parallel routing algorithm for large-scale high-speed switching systems in this paper. Starting from the edge coloring problem of bipartite graphs, this paper first presents algebraic edge coloring approach, based on which we design the scheduling and routing algorithms. Our simulation results show that these algorithms possess the following features: 1) They have a low computation complexity; 2) They can provide 100% throughput; 3) They can achieve end-to-end delay in microseconds; 4) They do not require any hardware acceleration, and do not lead to packet out-of-sequence problem.

A route assignment algorithm for fault-tolerant Clos networks, which is commonly used for design of optical switches, is proposed in this paper. The algorithm is based on a newly proposed edge coloring method, called complex coloring. The route assignment in three-stage fault-tolerant Clos networks is formulated as an edge coloring problem of bipartite graphs. The extra switch modules in the middle stage of fault-tolerant Clos networks provide additional colors for edge coloring. In complex coloring, those redundant colors help to reduce the running time of the coloring process. Therefore, as the number of extra switch modules increases, the time complexity can be substantially improved along with the reliability of switching systems. The performance of our algorithm has been verified by extensive simulation experiments.

The edge coloring problem of graphs has interesting real life applications in the optimization and the network design, such as the file transfers in computer networks. A $k$-edge coloring of a graph $G$ is a mapping $\phi: E(G) \rightarrow \{1,\cdots,k\}$. Let $f(v)$ denote the sum of the colors on all the edges incident to $v$. A $k$-neighbor sum distinguishing edge coloring of $G$ is a $k$-edge coloring of $G$ such that for each edge $uv\in E(G)$, $f(u)\neq f(v)$. The neighbor sum distinguishing index of a graph $G$ is then the smallest $k$ for which $G$ admits a $k$-neighbor sum distinguishing edge coloring. In this paper, we study the equitable neighbor sum distinguishing edge coloring, it is a $k$-neighbor sum distinguishing edge coloring $\phi$ for which the number of edges in any two color classes of $\phi$ differ by at most one. The smallest value $k$ in such a coloring of $G$ is called equitable neighbor sum distinguishing index, denoted by $\overline{\chi^{e}_{\sum}}(G)$. Exact value of $\overline{\chi^{e}_{\sum}}(G)$ are determined for several classes of graphs, including cycles, fan graphs and theta graphs.

This paper considers the minimum coloring problem by using the matrix semi-tensor product, and obtains a number of new results and algorithms. Firstly, the minimum coloring problem is expressed into a kind of optimization problem taking in an algebraic form of matrices, based on which an algorithm is designed to find all the minimum coloring schemes for any simple graph. Secondly, an equivalent problem of minimum coloring problem is studied, and a necessary and sufficient condition is proposed, from which a new algorithm to find all the minimum coloring schemes is established. Finally, the effectiveness of the results/algorithms presented in this paper is shown by one illustrative example.

It is shown that the hypergraph generated by a hexagonal system is conformal if and only if the hexagonal system is catacondensed. Also, it is shown that the chromatic index of the hypergraph generated by a catacondensed hexagonal system is five. Finally, a formula for the covering number of the hypergraph generated by a catacondensed hexagonal system is given.

A coloring of a graph is an assignment of colors to its nodes so that no two adjacent nodes are assigned the same color. Given a graph G, by a Grundy k-coloring of G mean any proper k-vertex coloring of G such that for each two colors i and j, i< j, every vertex of G colored by j has a neighbor with color i. The maximum k for which there exists a Grundy k-coloring is denoted by Γ (G) and called Grundy (chromatic) number of G. In this paper the authors introduce Grundy colorings and the authors give two algorithms to maintain the Grundy coloring of any graph G when a changement has been occurred (an edge is added or broken).

A system with the property of self-stabilization can have the advantages of fault tolerance, robustness for dynamic topologies, and straightforward initialization. This paper propose a new self-stabilizing algorithm for the proper coloring of edges using a maximum Δ + 1 colors and convergence time O (m (n + Δ)).

Analyzing chromatic number in coloring problem is a tough topic in graph analysis. We focus on the basic theory for a particular type of chromatic number. This will give us insights on the basic topological structure guiding lots of networks in the coming trend of big data era. An adjacent vertex-distinguishing total k-coloring is a proper total k-coloring of a graph G such that for any two adjacent vertices, the set of colors appearing on the vertex and its incident edges are different. The smallest k for which such a coloring of G exists is called the adjacent vertex-distinguishing total chromatic number, and denoted by ?at(G). It has been proved that if the graph G satisfies ?(G)=3, then ?at(G)= 6. However, it is very difficult to determine whether ?at(G)= 5. In this paper, we focus on a special class of 3-regular graphs, the generalized Petersen graphs P(n, k), and show that ?at(P(n, k)) = 5, which improves the bound ?at (P(n, k))= 6.

Graph coloring is a fundamental NP-hard problem in graph theory. It has a wide range of real applications, such as Operations Research, Communication Network, Computational Biology and Compiler Optimization. Notable efforts have been spent on designing its approximation algorithms. Halldrsson proposed the algorithm (denoted as SampleIS) with the current best known approximation ratio. However, its time complexity is O(|G|3), where |G| is the number of vertices of a graph G. It is clear that SampleIS is not practical for large graphs. In this paper, we propose a practical vertex-cut based coloring technique (VColor) for coloring large graphs. First, we partition G into k connected components (CCs) of a small size s by removing a vertex-cut component (VCC). For each CC, we apply our novel coloring algorithm, based on maximal independent set enumeration. The approximation ratio and the time complexity for coloring the k CCs are log s + 1 and O(ks23s/3), respectively, whereas those of SampleIS are ks(log log ks)2/ log3 ks and O(k3s3). For the VCC, we simply apply SampleIS. To combine the colorings of the CCs and the VCC, we propose a maximum matching based algorithm. Second, in the context of a database of graphs, users may color many graphs. We propose an optimization technique, inspired by multi-query optimization, for coloring a set of graphs. We design a VP hierarchy (VPH) to represent the common subgraphs as the common CCs. Third, we propose techniques for determining the optimal values of the parameters of VColor. Our extensive experimental evaluation on real-world graphs confirms the efficiency and/or effectiveness of our proposed techniques. In particular, VColor is more than 500 times faster than SampleIS, and the number of colors used are comparable on real graphs Yeast and LS.

Although there is an extensive literature on GPU implementations of graph algorithms, we do not yet have a clear understanding of how implementation choices impact performance. As a step towards this goal, we studied how the choice of synchronization mechanism affects the end-to-end performance of complex graph algorithms, using stochastic gradient descent (SGD) as an exemplar. We implemented seven synchronization strategies for this application and evaluated them on two GPU platforms, using both road networks and social network graphs as inputs. Our experiments showed that although none of the seven strategies dominates the rest, it is possible to use properties of the platform and input graph to predict the best strategy.

A graph G is said to have a dominator coloring if it has a proper coloring in which every vertex of the graph dominates all vertices of atleast one color class. The dominator chromatic number Xd (G) is the least number of colors required for a dominator coloring of G. The dominator chromatic number for Quadrilateral Snake graph, Triangle Snake graph and Barbell graph are derived and also the relationship between chromatic number, domination number and dominator chromatic number of these graphs are shown in this paper.

Given an undirected graph with a set of vertices and edges, vertex coloring, a well-known classical optimization problem in graph theory, consists of partitioning all vertices into independent sets and assigning unique colors to adjacent vertices with an effort to use the least number of colors. This paper presents a new algorithm based on artificial bee colony for solving the aforementioned problem. The proposed algorithm is evaluated on the DIMACS challenging benchmarks and computational results show that the presented method achieves highly competitive results. The outstanding outcomes of our algorithm are related to its computational time and also the number of colors it uses. Our simulations show that the computational time is considerably short and also the number of colors for vertex coloring is optimal in most of the cases.

In this paper a new formulation of the robust graph coloring problem (RGCP) is proposed. In opposition to classical GCP defined for the given graph G(V,E) not only elements of E but also E can be subject of color conflicts in edge vertices. Conflicts in E are assigned penalties 0

The channel assignment problem in mobile networks can be modeled as a temporal graph coloring problem where a temporal graph represents a sequence of graphlets generated over a regular interval of time. The cost of coloring a graphlet is defined as a function of number of colors used in the current graphlet and the number of color changes from the previous graphlet. A differential coloring technique is proposed which first finds the minimum number of vertices that requires recoloring and then recolor them. A prediction based and a random coloring based approaches are proposed to reduce the cost. In prediction based approach, we predict a graph which is a supergraph of the graph representing the union of current and next k graphlets and then color it. Whereas, in random coloring we color the graphlets individually. We have shown that both approaches perform better than an existing SNAP algorithm.

This paper considers the fuzzy graph coloring problem. Using the matrix semi-tensor product, two necessary and sufficient conditions are put forward for the fuzzy colorability, based on which a new algorithm is designed to find all the fuzzy coloring schemes for any fuzzy graph. the effectiveness of the results/algorithms presented in this paper is shown by one illustrative example.

We consider the state space explosion problem which is a fundamental obstacle in formal verification of critical systems. In this paper, we propose a fast algorithm for distributing state spaces on a network of workstations. Our solution is an improvement version of SSCGDA algorithm (for Strict Strong Coloring based Graph Distribution Algorithm) which introduced the coloring concept and dominance relation in graphs for finding the good distribution of given graphs [1]. We report on a thorough experimental study to evaluate the performance of this new algorithm. The quality of the proposed algorithm is illustrated by comparison with existing algorithms.

The rainbow vertex - connection number, rvc(G), of a connected graph is the minimum number of colors needed to color its vertices such that every pair of vertices is connected by at least one path whose internal vertices have distinct colors. Rainbow coloring has received much attention recently in the field of interconnection networks. Computing the rainbow connection number of a graph is NP- hard and it finds its applications in the secure transfer of classified information between agencies and in cellular network. In this paper we characterize some families of cubic graphs and its strong rainbow connection numbers have been found.

For multi-hop wireless networks, we assign channels to communication between terminals. For this assignment problem, modeling using the edge coloring of the graph theory has been proposed. In the modeling, all edges of the graph are assigned colors. In this paper, we assign colors to edges in a subset of the edge set as the other modeling, and we consider the number of assigned colors in the graph. We show some theoretical results and examine this modeling with computer simulation.

We show that an effective version of Siegel's Theorem on finiteness of integer solutions and an application of elementary Galois theory are key ingredients in a complexity classification of some Holant problems. These Holant problems, denoted by Holant(f), are defined by a symmetric ternary function f that is invariant under any permutation of the k >= 3 domain elements. We prove that Holant(f) exhibits a complexity dichotomy. This dichotomy holds even when restricted to planar graphs. A special case of this result is that counting edge k-colorings is #P-hard over planar 3-regular graphs for k >= 3. In fact, we prove that counting edge k-colorings is #P-hard over planar r-regular graphs for all k >= r >= 3. The problem is polynomial-time computable in all other parameter settings. The proof of the dichotomy theorem for Holant(f) depends on the fact that a specific polynomial p(x,y) has an explicitly listed finite set of integer solutions, and the determination of the Galois groups of some specific polynomials. In the process, we also encounter the Tutte polynomial, medial graphs, Eulerian partitions, Puiseux series, and a certain lattice condition on the (logarithm of) the roots of polynomials., 75 pages, 29 figures, 4 tables

An edge subset B is h-super edge-cut of a connected graph G if G - B is disconnected, moreover every vertex has at least h neighbors in G - B. Minimum |B| of G is h-super edge-connectivity of G, denoted by λ s (H) (G). In this paper, we determine λ s (H) (S n, k ) for 0 ≤ h ≤ n - k, where S n, k de-notes (n, k)-star graphs, so that we can get traditional edge-connectivity λ (S n, k ) and λ s (S n, k ) and get edge-connectivity of n-star graphs S n who is isomorphic to S n, n-1 . In fact, the conclusions of generalized edge-connectivity in the known graphs are few, so this work is very valuable.

This paper studies the online channel assignment problem arising in dynamic wireless networks. The goal is to assign channels to communication links such that interference (or the number of conflicts) in the network is minimized. We model the problem as an online edge coloring problem. This problem is NP-hard by a reduction from EDGE COLORING. We present an online distributed greedy algorithm that gives a solution with at most 2(1 - 1/k)|E| more conflicts than the optimal solution, which implies a (2 - 1/k)-approximation. We then show that this ratio is tight by proving a lower bound that matches the above ratio.

The Maximal Independent Set (MIS) formulation tackles the graph coloring problem (GCP) as the partitioning of vertices of a graph into a minimum number of maximal independent sets as each MIS can be assigned a unique color. Mehrotra and Trick [5] solved the MIS formulation with an exact IP approach, but they were restricted to solving smaller or easier instances. For harder instances, it might be impossible to get the optimal solution within a reasonable computation time. We develop a heuristic algorithm, hoping that we can solve these problems in more reasonable time. However, though heuristics can find a near-optimal solution extremely fast compared to the exact approaches, there is still significant variations in performance that can only be explained by the fact that certain structures or properties in graphs may be better suited to some heuristics more than others. Selecting the best algorithm on average across all instances does not help us pick the best one for a particular instance. The need to understand how the best heuristic for a particular class of instance depends on these graph properties is an important issue. In this research, we use data mining to select the best solution strategies for classes of graph coloring instances.

Graph coloring problem is a classical example for NP-hard combinatorial optimization. Solution to this graph coloring problem often finds its applications to various engineering fields. This paper exhibits the robustness of genetic algorithm to solve a graph coloring. The proposed genetic algorithm employs an innovative single parent conflict gene crossover and a conflict gene mutation as its operators. The time taken to get a convergent solution of this proposed genetic method has been compared with the existing approaches and has been proved to be effective. The performance of this approximation method is evaluated using some benchmarking graphs, and are found to be competent.

In this paper, graph coloring has been done using artificial bee colony (ABC) optimization algorithm. Graph coloring deals with the challenge of coloring the nodes of any graph by least possible number of colors while ensuring on same time that two adjacent nodes does not gain same color. That least possible count of colors used denotes the chromatic number of a graph and to determine this number for any graph is an NP-complete problem hence no existing polynomial time algorithm can solve it. To find the best coloring sequence, a large search space has to be explored. Graph coloring deals with the challenge of coloring the nodes of any graph by least possible number of colors while ensuring on same time that two adjacent nodes does not gain same color and proposed a novel artificial bee colony (ABC) optimization algorithm for graph coloring. In this paper, we analyzed the proposed algorithm and compared it with three other graph coloring algorithms i.e. first fit, largest degree based ordering (LDO) and saturation degree based ordering (SDO). These results also indicate that ABC algorithm converges in a few iterations and is able to optimally allocate colors to vertices of a graph.

An undirected graph can demonstrate adjacency relationships among regions in a planar map, and the four-coloring map problem is then converted into a graph vertex coloring problem with constraints. In order to solve the graph vertex coloring problem, an ant algorithm hybridized with a greedy algorithm was proposed. In this algorithm, ants in an ant colony with a given size separately move from one vertex to another according to their transition probability, and a greedy algorithm is used to initialize the proposed algorithm for improving its efficiency. Finally, the improved algorithm was tested by coloring the administrative map of Hunan Province, China, and results show that it is good at finding the optimal value, speed and stability.

In the present paper, we consider fully asynchronous parallelism in membrane computing, and propose two asynchronous P systems for two graph coloring problems. We first propose an asynchronous P system that solves the k-coloring for a graph with n nodes, and show that the proposed P system works in O(k^nn^2) sequential steps or O(n^2) parallel steps using O(n^2) kinds of objects. We next propose an asynchronous P system that solves the minimum graph coloring for a graph with n nodes, and show that the proposed P system works in O(n^(n+2)) sequential steps or O(n^2) parallel steps using O(n^2) kinds of objects.

An acyclic coloring of a graph G is a coloring of the vertices of G, where no two adjacent vertices of G receive the same color and no cycle of G contains vertices of only two colors. An acyclic k-coloring of a graph G is an acyclic coloring of G using k colors. In this paper we show the necessary and sufficient condition of acyclic coloring of a complete k-partite graph. Then we derive the minimum number of colors for acyclic coloring of such graphs. We also show that a complete k-partite graph G having n 1 , n 2 ,…, n k vertices in its Ρ 1 ,Ρ 2 ,…, P k partition respectively is acyclically (2k − 1)-colorable using ∑ i≠j, i, j≤k n i n j + n max + (k−1) − ∑k−1 i=0 (k−i)n i+1 division vertices, where n max = max(n 1 , n 2 ,…, n k ). Finally we show that there is an infinite number of cubic planar graphs which are acyclically 3-colorable.

Let G(V, E) be a simple connect graph with order not less than 3, k is an natural number and f is a mapping from V(G)iEE(G) to {1,2i­,k}.if for any uviEE(G), we have f(u) iUf(v),f(u) iUf(uv), f(v) iUf(uv); for any uv, uwiEE(G),(viUw),f(uv) iUf(uw);for any u, viEV(G)C(u)iUC(v), while C(u)={f(u)}iE{f(w)|uwiEE(G)} iE{f(uw)|uwiEE(G)}, C(v)={f(v)}iE{f(e)|veiEE(G)} iE{f(ve)|veiEE(G)}.Then f is called strong vertex-distinguishing total coloring of graph G(k-VSDTC of G if brief) and the number is called the strong vertex-distinguishing total chromatic number of G. In this paper, we design and implement an algorithm. It proves and gets the given point of complete graph of strong vertex-distinguishing total chromatic number.

An f-coloring of a graph G is a coloring of edges of E(G) such that each color appears at each vertex v ∈ V (G) at most f (v) times. The minimum number of colors needed to f-color G is called the f-chromatic index of G, and denoted by χ′f(G). Any graph G has f -chromatic index equal to Δf (G) or Δf (G)+1, where equation. If χ′f(G) = Δf(G), then G is of Cf 1; otherwise G is of Cf 2. The f -core of G is the subgraph of G induced by the vertices of equation. In this paper some results about the generalized Petersen graphs are presented.

Let ƒ be a proper total coloring of G. For each x ∈ V(G), let C(x) denote the set of all colors of the elements incident with or adjacent to x and the color of x. If ∀ u, v ∈ V(G), u ≠ v, we have C(u) ≠ C(v), then ƒ is called a vertex strongly distinguishing total coloring of G. The minimum number k for which there exists a vertex strongly distinguishing total coloring of G using k colors is called the vertex strongly distinguishing total chromatic number of G. The vertex strongly distinguishing total chromatic number of complete bipartite graph K 3,3 is obtained in this paper.

Theorem on 2-factorization of complete graph K 2n of even order is proved. Foundamental concepts of 1-factorization and 2-factorization of complete graphs K 2n are described. Construct the edge matrix of the complete graph K 2n , edge coloring has been followed, Thus the rectangular matrix has been composed by 1-factor of 2n−1. Determine the collocation programming which is let 2n−1 1-factor combined with n−1 2-factor and 1 1-factor and generated cycles for each 2-factor, In accordance with the different Programming, The process which let E(G) divide into n−1 frontier set of Hamiltonian cycles and 1 1-factor. The entire procedure of 2-factorization of complete graphs K′ 10 , K 12 and K 14 is presented.

We here present two probabilistic edge coloring algorithms for a message passing model of distributed computing. The algorithms use a simple automata for finding a matching on a graph to produce the colorings. Our first algorithm for edge coloring finds an edge coloring of a graph which is guaranteed to use no more than 2? - 1 colors and completes in O(?) communication rounds using only one hop information, where ? is the greatest degree of the graph. Our second algorithm finds a strong edge coloring of a symmetric digraph in O(?) communication rounds, using only one hop information.