Graph coloring
Published On :2021-10-27 19:50:00
Graph coloring
Motivation: Many real life problems can be modeled by graphs require that the vertex set or edge set
be partitioned into disjoint sets such that each items within a given set are mutually nonadjacent.
examples of these problems are schedule meeting, schedule
exams (to aviod conflict), storing chemicals (to prevent interactions), …
**1) Vertex coloring and independent sets:
Definition : A (proper) vertex coloring of a
graph G is an assigment of colors to the vertices so that adjacent vertices have distinct colors.
* A vertex coloring using k colors is called k-coloring.
* A graph that permits a k-coloring is called k-colorable.
Ex:
PHOTO
So we have 3-coloring of G & we say G is 3-colorable.
Note that we can use only two colors to color G.
Note that we can use only two colors to color G.
PHOTO
Thus we have 2-coloring of G & we say G is 2-colorable.
Def: The chromatic number of a graph G, denoted by X(G), is the
minimum number of colors needed for any proper k-coloring of G.
Ex: In previous example,
PHOTO
Observe that the minimum number of colors to have a proper coloring of G equals 2.
Remark:(1) If G is connected, then X(G) >= 2 .
(2) We have seen before, graph G is bipartite iff X(G) = 2 .
Ex: Find the chromatic number of C40 , Qn & T where T is any tree.
Observe that C40 , Qn & T are bipartit graphs. Thus
X(C40) = 2 ,
X(Qn) = 2 ,
& X(T) = 2 , for anytree T.
X(Kn) = n , for all n.
If we color a vertex v of Kn , then
we can’t reuse this color & this is because all the other vertices of Kn are adjacent to v.
Thus each vertex will have a different color.
Remark: If G is a graph of order n & G is not Kn, then X(G) < n.
( Since G does’t equal , then G has two vertices say u & v that are not adjacent. We color
u & v with the same color & thus we need less than n colors to color G)