Answer To: Writing Project Topics Here is a list of places in the text to look for writing project...
Robert answered on Dec 23 2021
Graph Coloring
Let G = (V, E) represent a graph with vertex set V and edge set E formed by all pairs of incompatible
Elements.
The problem says; suppose that V contains certain pairs of elements that are incompatible. Our aim is to
find a partition of V into a minimal number of subsets of mutually compatible elements.
When we talk about partitioning of V into k subsets, it is equivalent to coloring the vertices of G with k
colors.
A (vertex) colouring of a graph G is a mapping C : V(G) → S.
The elements of S are called colours; the vertices of one colour form a colour class. The colour classes
divide V into independent subsets ; subset of pair wise non-adjacent vertices.
If |S| = k, we say that c is a k-colouring (often we use S = {1, . . . , k}).
A colouring is proper when no two vertices share the same colour.
A graph is k-colourable if it has a proper k-colouring. The chromatic number X(G) is the least k such that
G is k-colourable. Obviously, X(G) exists as assigning distinct colours to vertices yields a proper
|V(G)|-colouring.
An optimal colouring of G is a X(G)-colouring. A graph G is k-chromatic if X(G) = k.
The problem of determining X(G), the chromatic number, is an NP - complete.
An NP - complete problem has no polynomial time algorithm.
A 3-colour example of a vertex colouring is shown below :
Chromatic Polynomial :
A chromatic polynomial counts the number of ways a graph can be colored, using no more than the
number of colours given. That is, it counts the number of its proper vertex colourings.
We have used X(G) to denote a chromatic number.
A chromatic polynomial can be represented as P(G, k) where G represents the graph, and k denotes the
number of colours. Thus, for a given G, the function is a polynomial in k.
for example :
P(G, k) = k(k-1)(k-2)(k-3)
=> P(G, 4) = 24
The chromatic polynomial P(G, k) and the chromatic number X(G) are related. the chromatic number is
the smallest positive integer that is not a root of the chromatic polynomial,
X(G) = min { k : P(G, k) > 0 }
Common Properties of P(G, k) :
Evaluating the chromatic polynomial in P(G, k) yields the number of k-colorings of G for k = 0, 1, 2, .. , n
for all n є N.
In the graph G; n be the number of vertices, m be the edges and s be the components G1, G2, .., Gs. Then
:
The...