Vertex Coloring

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₄  and W₅

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₄     ) = 3 and X (  W₅    ) = 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

1. If G is critical, then the theorem is true for H    = G.
2.  If G is not critical, then there exists a proper subgraph of H₁  of G with χ(H₁) = χ(G).
3. if H₁ is critical, then we are done; H = H₁.
4. If H₁ is not critical there exists a proper subgraph of H₂  of  H₁ such that χ(H₂) = χ(H₁) = χ(G).
5. We continue in this manner. Since G is finite, for some k we must obtain a subgraph H_k such that H_k is critical. Then 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.

1. Suppose that the theorem is false.
2. 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.
3. Since G is critical, G − v can be colored with only three colors.
4. So we color G − v with three colors.
5. 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.
6. But this is a contradiction, since G has chromatic number four.
7. 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.

1. The proof is the same with theorem 2.1.3.a. ; instead of four we substitute  χ.
2. 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 ≤ 2q  holds.

1. By theorem 2.1.3, the degree of each vertex of G is at least χ – 1, and there are p vertices.
2. So the sum of the degrees of the vertices of the G is at least (χ – 1)p.
3. By theorem 1.1.1, the sum of the degrees of the vertices of G is equal to 2q.
4. 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₄ or W_n for 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_m,n, was defined in chapter 1.

The cube graph Q₃ 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.

1. 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.
2. 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?
3. Select a vertex x₀ of G. We color G as follows. If x is a vertex of G, we color x red if d(x₀,x) is even, and we color x blue if  d(x₀,x) is odd. (So for instance, since d(x₀,x₀) = 0, x₀ is colored red because 0 is even.)
4. Since every distance is either even or odd, every vertex is now colored.
5. Now we  must show that no two adjacent vertices have the same color. We consider two adjacent vertices x and y.
6. We choose a shortest path from x₀ to x and a shortest path from x₀ to 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 u may also be x or y.
7. 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.
8. 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.
9. Since  d(x₀,x) = d(x₀,u) + d(u,x) and d(x₀,y) = d(x₀,u) + d(u,y), d(x₀,x) and d(x₀,y) also have different 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.

Related Post