Title:	A linear Programming Approach to The Maximum Clique Problem

Abstract:  Let G be a graph with nodes 1,...,n  and let  w 
denote the size of the largest clique in G. 
For each node v in G let G(v) denote the graph
induced by v and its neighbors in G. It is clear that the largest clique
in all the graphs G(v) is also the largest clique in G. It is well-known
that if G(v) is perfect its largest clique can be found in polynomial
time. Thus the largest clique in G can be found in polynomial time if
each of the graphs G(v) is perfect. We formulate a linear programming
problem whose solution gives the largest clique in G even if some of the
graphs G(v) are imperfect. In fact it gives the largest clique in G if
not more than  w of the graphs G(v) are imperfect.