China
Africa
Explore chapters and articles related to this topic
Total Global Dominator Coloring of Graphs
Published in N. P. Shrimali, Nita H. Shah, Recent Advancements in Graph Theory, 2020
A graph coloring is an assignment of colors to the vertices or edges or both of a graph G. The minimum number of colors required to color the vertices of a graph G such that the adjacent vertices possess different colors is known as the chromatic number of G and is denoted by χ(G). A coloring of a graph G with χ(G) colors is called the chromatic coloring or χ − coloring of G. Let {V1, V2, V3…, Vk} be a partition of vertex set V with respect to a coloring c such that a vertex v ∈ Vi if c(v) = ci then Vi is called the color class of v with respect to c.
Graph Colorings
Published in Jonathan L. Gross, Jay Yellen, Mark Anderson, Graph Theory and Its Applications, 2018
Jonathan L. Gross, Jay Yellen, Mark Anderson
In the most common kind of graph coloring, colors are assigned to the vertices. From a standard mathematical perspective, the subset comprising all the vertices of a given color would be regarded as a cell of a partition of the vertex-set. Drawing the graph with colors on the vertices is simply an intuitive way to represent such a partition.
A green proactive orchestration architecture for cloud resources
Published in International Journal of Computers and Applications, 2019
The proposed global controller formulated the considered multi-objective VMs placement challenge as a graph coloring-based methodology. Graph coloring is considered as one of the most important concepts in graph theory that is widely used in various real-time applications [35]. Graph coloring is NP-complete problem and is defined as coloring the vertices of a graph without any two adjacent vertices having the same color. More specifically, coloring of an undirected graph G = (V, E) is the process of assigning to each vertex vi ∈ V a color c(i), such that, for every edge [vi, vj] ∈ E c(i) ≠ c(j) [36]. Conceptually, graph coloring is the problem of determining a coloring scheme which uses as few colors as possible. The chromatic number χ (G) of a graph is the least number of colors required for a proper vertex coloring of G [37,38].
A scalable Bayesian framework for large-scale sensor-driven network anomaly detection
Published in IISE Transactions, 2023
The next step is to find the clusters and variables within clusters that can be sampled together. To do that, we can borrow an idea from the well-known graph coloring problems, which have many applications in mathematics and computer science. In graph coloring problems, vertex coloring is conducted so that no two adjacent vertices share the same color. Considering the pseudo-adjacency matrix, we can use graph coloring to find the set of nodes that can be sampled together (nodes that are not in the MB of others). We utilize a fast greedy approach inspired by Wang et al. (2017) that considers the unknown nodes of the BN based on a predefined sequence and then assign each node its first available color (cluster number). The idea is to first find the sink nodes, which are the nodes without outgoing edges (children), and then start from the one with the minimum degree. Once the independent sink nodes are chosen (with regards to their MB), they are removed from the network and the process continues until all nodes are assigned to the clusters. When arriving at a node, we check all existing clusters to verify if an assignment to them is possible. If not (because at least one of the nodes in each cluster is within the MB of the existing node), then we build a new cluster and move on. The details of the graph clustering for parallelization are given in Algorithm 2. The outcome of this algorithm is C clusters, denoted by and the variables in each cluster. It is clear that for any pair and This algorithm works for both tree and non-tree structures. Also, it is possible that there is more than one way to cluster a network. In Figure 5, we provide a simple example of a 10-node tree graph and a 13-node non-tree graph to show which nodes can be sampled together based on the algorithm. Based on this graph, there are a total of four clusters with 6, 2, 1, and 1 nodes for the tree graph and a total of six clusters with 5, 3, 2, 1, 1, and 1 nodes for the non-tree graph. The nodes within each cluster can be sampled together. It is interesting to note that in the context of power distribution networks, devices of the same type can be clustered together, as they are not within each other’s MB. For instance, all meter nodes can be sampled simultaneously, then transformer nodes can be sampled together, and so on (see Figure 1 in Supplemental Materials).