Proper
Coloring

Improper
Coloring

Given a graph G, find a coloring of the
vertices so that no two neighbors in G have the same color

INTRODUCTION

Vertex
Coloring : The wheel
with n spokes, W

_{n }is the graph that consist of an n – cycle and one additional vertex that is adjacent to all the vertices of the cycle.. In Figure 2.1.1 we display W_{4 }and W_{5}
DEFINITION OF
VERTEX COLORING: Given a graph G, we define a coloring of G to be an assignment of colors
to the vertices of G such that no two adjacent vertices receive the same color.

CHROMATIC
NUMBER:

What is : If G has p vertices we can color G with p colors.

Chromatic
number: We denote the minimum number of colors necessary to
color G by X( G ), the chromatic number of tghe graph G.

X( G ) = n
means the graph G is colorable by n colors, and G is not colorable by n – 1
colors. Example in figure 2.1.1, X (W

_{4}) = 3 and X ( W_{5}) = 4.
The only graph
with p vertices and chromatic number equal to p is K

_{p}
For Instance,
what is the chromatic number of the raph G in figure 2.1.2 ?

We see that
there is a subgraph isomorphic to K4. Thus X(G)≥4

Let G be a graph, and let v be a vertex of G. If we remove v and all the
edges incident with v from G, the resulting graph is called G – v. Similarly,
if e is any edge of G, the graph obtained from G by removing e is G – e. We
leave all the vertices in G when we remove an edge. If v is a vertex of K

_{p}, then K_{p}- v is isomorphic to K_{p-1}. If G is the graph in figure 2.1.2, G – a is the graph in Figure 2.1.3 and G – e is the graph in Figure 2.1.4
Critical
Graph:

Let

*G*be a graph. If*H*is a subgraph of*G*, and*H*≠*G*, then*H*is called a*proper subgraph*of*G*. if χ(*H*) < χ(*G*) for every proper subgraph*H*of*G*, then we say that*G*is critical.
The graphs of
Figures 2.1.2 and 2.1.5 are critical, and the complete graph

*K*_{n}is also critical for every n.
Theorem 2.1.1:
Every critical graph is connected.

Theorem 2.1.2: Every graph

*G*contains a critical subgraph*H*such that χ(*H*) = χ(*G*).
THEOREM

- If
*G*is critical, then the theorem is true for*H*=*G*. - If
*G*is not critical, then there exists a proper subgraph of*H*of_{1}*G*with χ(*H*) = χ(_{1}*G*). - if
*H*is critical, then we are done;_{1}*H*=*H*._{1} - If
*H*is not critical there exists a proper subgraph of_{1}*H*of_{2}*H*such that χ(_{1 }*H*) = χ(_{2}*H*) = χ(_{1}*G*). - We continue in this manner. Since
*G*is finite, for some*k*we must obtain a subgraph*H*_{k}_{ }such that*H*is critical. Then_{k}*H*=*H*._{k}

Theorem
2.1.3.a : If

*G*is critical with chromatic number four, then the degree of each vertex is at least three.- Suppose that the theorem is false.
- Then there exists a critical graph
*G*with chromatic number four and a vertex*v*of*G*such that the degree of*v*is at most two. - Since
*G*is critical,*G*−*v*can be colored with only three colors. - So we color
*G*−*v*with three colors. - We put the vertex
*v*back;*v*is adjacent to at most two vertices, so there is at least one of the three colors left to color*v*. - But this is a contradiction, since
*G*has chromatic number four. - Thus the degree of each vertex is at least
three.

Theorem
2.1.3.b : If

*G*is critical with chromatic number χ, then the degree of each vertex is at least χ – 1.- The proof is the same with theorem 2.1.3.a. ;
instead of four we substitute χ.
- Another example that illustrates the more
general theorem is the critical graph of Figure 2.1.2, where χ = 5, and
the degree of each vertex is at least four.

Theorem 2.1.4.: If

*G*is a critical graph with*p*vertices and*q*edges, and*G*has chromatic number χ, then the relation (χ − 1)*p*≤ 2*q*holds.- By
theorem 2.1.3, the degree of each vertex of
*G*is at least χ – 1, and there are*p*vertices. - So the
sum of the degrees of the vertices of the
*G*is at least (χ – 1)*p*. - By
theorem 1.1.1, the sum of the degrees of the vertices of
*G*is equal to 2*q*. - Hence
theorem 2.1.4 is proved.

NOTE :

The graph in Figure 2.1.7 is also critical. There
exists graphs of arbitrarily high girth and arbitrarily high chromatic number
[7],[17].

We know that if a graph

*G*contains a subgraph isomorphic to*K*_{4}or*W*for_{n}*n*odd, then χ(*G*) ≥ 4.
The graphs in Figures 2.1.6 and 2.1.7 also have
chromatic number 4, but they contain no triangles, and that makes it hard to
check that the two graphs are not colorable by three colors.

The girth of a graph is the length of a shortest
cycle in the graph. The girth of the graphs in Figure 2.1..6 and 2.1.7 is four.

Theorem 2.1.5: (

*ErdÖs-Lovász*). For every two integers*m*,*n*≥ 2, there exists a graph with chromatic number*n*whose girth exceeds*m*.
NOTE :

Let

*G*be a graph, and let*x*and*y*be vertices of*G*. The distance from*x*to*y*in*G*, denoted by*d(x,y),*is the length of a shortest path from*x*to*y*. If there is no path from*x*to*y*, we say*d(x,y)*= ∞. In Figure 2.1.2,*d(a,b)*= 2,*d(a,c)*= 1.
An unsolved coloring problem is the following
conjecture of Lovász. If

*G*is graph such that χ(*G*–*v*–*w*) = χ(*G*) – 2 for every pair of adjacent vertices v and w, then*G*is a comlete graph. Exersize 2.1.3 is a modified version of this problem. It differs by only one word, but it is much easier to prove.
A graph

*G*is called bipartite if χ(*G*) ≤ 2. A special example of a bipartite graph, the complete bipartite graph*K*, was defined in chapter 1._{m,n}
The cube graph Q

_{3}of Figure 1.2.5 is another example of a bipartite graph, but the dodecahedron graph is not
Theorem 2.1.6. : graph

*G*is bipartite if and only if every cycle in*G*has even length.- Assume
that
*G*is bipartite. Suppose that*G*contains an odd cycle*C*. Then χ(*C*) = 3. Thus χ(*G*) ≥ 3, but this is a contradiction since*G*is bipartite. Hence*G*can not contain an odd cycle. - Now
assume that
*G*is a graph with no odd cycles. Without loss of generality, we assumed that*G*is connected. Why can we do this? - Select a
vertex
*x*of_{0}*G*. We color*G*as follows. If*x*is a vertex of*G*, we color*x*red if*d(x*is even, and we color x blue if_{0},x)*d(x*is odd. (So for instance, since_{0},x)*d(x*= 0,_{0},x_{0})*x*is colored red because 0 is even.)_{0} - Since
every distance is either even or odd, every vertex is now colored.
- Now
we must show that no two adjacent
vertices have the same color. We consider two adjacent vertices
*x*and*y.* - We choose
a shortest path from
*x*to_{0}*x*and a shortest path from*x*to_{0}*y.*let*u*be the last common vertex in these shortest paths. (See Figure 2.1.8.) The vertex*u*may be equal to*x*, or_{0}*u*may also be*x*or*y*. - Now we
consider
*d(u,x)*and*d(u,y).*If*u*is one of*x*or*y*, then either*d(u,x)*=*d(u,y)*+ 1 or*d(u,x)*=*d(u,y)*– 1. In either case, one of the distances is odd and one is even. We say they have different*parity*. - If
*u*is not one of*x*or*y,*we now compute the length of the cycle in Figure 2.1.8. It is*d(u,x)*+ 1 +*d(u,y).*We know this is even. Hence*d(u,x)*and*d(u,y)*have different*parity*. - Since
*d(x*=_{0},x)*d(x*+_{0},u)*d(u,x)*and*d(x*=_{0},y)*d(x*+_{0},u)*d(u,y)*,*d(x*and_{0},x)*d(x*also have different_{0},y)*parity*. Thus*x*and*y*receive different colors, and χ(*G*) ≤ 2, so*G*is bipartite.

Theorem 2.1.6 shows that trees are bipartite. Every
cycle in a tree has even length, since there are no cycles in a tree. In other
words, if there is a cycle in a tree, then the cycle has even length. An
“if-then” statement is always true if there is no circumstance that makes the
“if” part true. Such a statement is vacuously true. We give you a strange
example. All my violins have length. This is true since I have no violins. See
also exercise 2.1.8.

The
diameter of a graph G is the maximum
distance between any two vertices of G.
For instance, the diameter of Pn is n; the diameter of Wn is 2 if n > 3; the
diameter of Kn is 1; and the diameter of Km,n is 2 if m or n is at least two.
In applications of graph theory to communications networks, diameter is important.
One wishes to have a graph with small diameter and as few edges as possible,
together with certain other restrictions. This is a very active area of
research now.

**dan anda bisa menemukan artikel Vertex Coloring ini dengan url**

__Vertex Coloring__**http://zakylubismy.blogspot.com/2014/06/vertex-coloring.html**,anda boleh menyebar luaskannya atau mengcopy paste-nya jika artikel

**Vertex Coloring**ini sangat bermanfaat bagi teman-teman anda,namun jangan lupa untuk meletakkan link

__Vertex Coloring__sumbernya.

## 0 komentar:

Poskan Komentar