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.
Introduction to Graph Theory
Published in Sriraman Sridharan, R. Balakrishnan, Foundations of Discrete Mathematics with Algorithms and Programming, 2019
Sriraman Sridharan, R. Balakrishnan
A coloring of the graph G with three colors B (for blue), y (for yellow), R (for red) with the property that no two vertices joined by an edge (or line segment) receive the same color (see color e-book). The reader may observe that 3 is the minimum number of colors needed to color the vertices of the graph G with the constraint imposed. In other words, three is the chromatic number of the graph G. Notice an important property of the graph: no two edges intersect at a point of the plane except at a vertex of the graph G. A graph admitting such a drawing is called a planar graph. For example, the graph of Figure 4.1 is planar (by redrawing the arc u9 $ u_9 $ without cutting u6 $ u_6 $ and u7 $ u_7 $ ). We now state the four-color theorem:
Graphs and Surfaces
Published in Kenneth H. Rosen, Graphs, Algorithms, and Optimization, 2005
This theorem gives χ(G) ≤ 7 for the torus. An embedding of K7 in the torus is shown in Figure 13.17, so that seven colors are necessary for the torus. We say that the chromatic number of the torus is seven, because all toroidal graphs can be colored in at most seven colors, and seven colors are necessary for some graphs. The dual of the embedding of K7 on the torus is the Heawood graph. Heawood was coloring the faces of an embedding rather than the vertices of a graph, and discovered this graph. The 4-color theorem tells us that the chromatic number of the plane is four. The formula of Heawood’s theorem gives the bound χ(G) ≤ 4 for the plane. However, the proof is invalid when g = 0, and there are many planar graphs other than K4 which require four colors. Lemma 13.25 gives g{Kn) ≥ ⌈(n – 3)(n – 4)/12⌉. A proof that g(Kn) equals this bound would mean that Kn can always be embedded in a surface of this genus. Since χ(Kn) = n, the inequality of Heawood’s theorem could then be replaced by an equality. Calculating the genus of Kn was accomplished by a number of people (Heffter, Gustin, Ringel, Youngs, and Mayer) over many years. We state the result, without proof, as the following theorem.
Length-constrained cycle partition with an application to UAV routing*
Published in Optimization Methods and Software, 2022
Kai Hoppmann-Baum, Oleg Burdakov, Gioni Mexi, Carl Johan Casselgren, Thorsten Koch
Let H be a hypergraph. The chromatic number is the minimum number of colors needed to color the vertices such that no hyperedge is monochromatic, i.e. each hyperedge contains vertices of at least two colors.