A note on graphs contraction-critical with respect to independence number

Let α ( G ) denote the independence number of graph G , i.e., the size of any maximum independent set of vertices. A graph G is contraction-critical (with respect to α ) if α ( G / x y ̂ ) < α ( G ) , for every edge x y ∈ E ( G ) , where G / x y ̂ denotes the graph obtained from G by shrinking the edge x y to a single vertex x y ̂ and deleting the loop thus formed. Let us denote the class of all such contraction-critical graphs by C C R . it is shown that all graphs in C C R must be bipartite. = ( A , B ) be a bipartite graph with bipartition A ∪ B . It is then shown that (a) if | A | < | B | , then G ∈ C C R if and only if B is the unique maximum independent set in G if and only if G is 1-expanding, while (b) if | A | = | B | , then G ∈ C C R if and only if A and B are the only two maximum independent sets in G if and only if G is 1-extendable. lows that C C R graphs can be recognized in polynomial time.