In-class Exercise 51. (a) What are the clique and independence numbers of A, B,
ID: 3038818 • Letter: I
Question
In-class Exercise 51. (a) What are the clique and independence numbers of A, B, C, D, G, and G from the previous problem? How do omega and |V|/alpha compare to chi for each graph? (b) What are the clique and independence numbers of (i) K_n, (ii) K_m, n, (iii) C_n, (iv) W_n, (v) Q_n, (vi) The Petersen graph? How do omega and |V|/alpha compare to chi for each graph? (You may need to break into cases.) (c) Explain why the clique number of the complement of a bipartite is no smaller than the number of vertices in each part. (Recall that the parts of a bipartite graph are the two collections of pairwise non-adjacent vertices.) (d) Notice that the graph is bipartite, so should have chromatic number 2. Now color this graph using the so-called "greedy algorithm": name your colors "color 1, color 2, ...". First color x_1 with color 1: then color x_2 with the lowest color possible (i.e. color 1 if you can, but color 2 if you can't); then color x_3 with the lowest color possible; and so on. How many colors did you need? What is a better way to color G?Explanation / Answer
A clique, C, in an undirected graph G = (V, E) is a subset of the vertices, C V, such that every two distinct vertices are adjacent. This is equivalent to the condition that the induced subgraph of G induced by C is a complete graph. In some cases, the term clique may also refer to the subgraph directly.
S V is independent if no edge of G has both of its endpoints in S. (G)=maximum size of an independent set of G.
(b)(i) n R(k1, k2, . . . , km) implies that if the edges of Kn are coloured with {1, 2, . . . , m} then i : Kn
contains a ki-clique all of whose edges have colour i.These numbers exist and satisfy
(ii) R(k1, k2, . . . , km) R(k1 1, k2, . . . , km)+ R(k1, k2 1, . . . , km)+ +· · ·+R(k1, k2, . . . , km1)(m2)
A graph is Km free if it contains no clique of size m (or more). m = 3 – triangle free. K[/2,v/2] has no triangles and no triangle free graph with vertices has more edges.
(iii) The set of b comparisons defines a b-edge graph G on a vertices where comparison of xi, xj produces an edge ij of G. Theorem 10 implies that (G) [b/(2a/b+1)] = [b2/(2a +b)]
For any independent set I it is always possible to define values for x1, x2, . . . , xa such I is the index set of the |I| largest values and so that the comparisons do not yield any information about the ordering of the
elements xi,i I. Thus after one round one has the problem of finding the maximum among (G) elements.
Kn is the symbol for a complete graph with n vertices, which is one having all (C(n,2) (which is n(n-1)/2) edges.
A graph that can be partitioned into k subsets, such that all edges have at most one member in each subset is said to be k-partite, or k-colorable. Thus a bipartite or two colorable graph is one whose vertex set V can be split into two parts, and all edges contain one vertex from each part.
Kn,m is the notation we use for a complete bipartite graph between vertex sets of size n and m. Thus it consists of all edges with one vertex among the m and the other among the n, and no edges within each of these two sets.
A simple basic question is: under what circumstance is a graph bipartite, (that is, two-colorable)?
We can give an ‘excluded configuration’ condition for bipartness or two colorability.
A graph will be two colorable if it has no odd length cycle.
If a graph has an odd length cycle, then it cannot be two colorable.
Suppose G has a cycle. If you start at a vertex v of color one of the cycle, if the graph were two colored then v’s neighbors including its neighbor, w, on its right in the cycle would have to have the other color, w’s neighbor on the right must have the first color and so on around the cycle. When you get back to where you start, v would have to have the opposite color than it had at first when the cycle has odd length, and this is a contradiction.
We can use a similar argument to prove that any graph that has no odd length cycle is bipartite. We get a coloring instead of a contradiction by coloring neighbors oppositely to oneself.
We can start anywhere by coloring one vertex v one color, v’s neighbors the other, their neighbors the first color, their neighbors the second color, and so on until every vertex that can be reached by a path from v is colored.
The absence of odd cycles means that each vertex reached will have the same color every time it is colored.
In a similar vein, it is not possible to color the complete graph, Kn, in fewer than n colors. In any coloring in fewer colors, two vertices must have the same color, but they will be in an edge, and this violates the condition on coloring that all edges contain vertices of different colors.
The minimum number of colors needed to color the vertices of a graph G so that none of its edges have only one color is called the coloring number of G.
A complete graph is often called a clique. The size of the largest clique that can be made up of edges and vertices of G is called the clique number of G.
On the other hand, the coloring number of a graph G can be strictly greater than its clique number, as we have already seen for C2j+1 when j is 2 or more. Such a graph has clique number 2 (which means it contains no triangle) but coloring number 3.
If the coloring number and clique number are the same for every induced subgraph of G, we call G a perfect graph.
The complement of a graph G is the graph on the same vertex set V, whose edges are precisely those that are not in the edge set of G.
Thus the edge set of G and of its complement include all the edges of the complete graph on V; and the edges of G and its complement do not overlap at all.
A famous result of graph theory is “The Perfect Graph Theorem” which reads:
A graph is perfect if and only if its complement is perfect.
By the way, the coloring number and clique number of the complement of G are parameters of interest by themselves.
The complement of G has all possible edges not in G. Thus a clique in the complement of G is a set of vertices among which there are no edges of G,