Let G be a graph with vertex set V (G) = {1, . . . , n} and edge set E(G). We are interested in studying the functions of the graph G whose values belong to the interval [ (G), (G)]. Here (G) is the size of the largest stable set in G and (G) is the smallest number of cliques that cover the vertices of G. It is well known (see, for example, [1]) that for some 0 it is impossible to approximate in polynomial time (G) and (G) within a factor of n , assuming P 6= NP. We suppose that better approximation could. | On the functions with values in G x G V. Dobrynin M. Pliskin and E. Prosolupov St. Petersburg State University St. Petersburg Russia vdobr pev @ Submitted Nov 25 2003 Accepted Mar 15 2004 Published Mar 22 2004 MR Subject Classification 05C50 Abstract Let B G X X E Rnxn X XT I X I A G and C G X X E Rnxn X XT I - A G X I A G be classes of matrices associated with graph G. Here n is the number of vertices in graph G and A G is the adjacency matrix of this graph. Denote r G minXeC G rank X r G minXeg G rank X . We have shown previously that for every graph G a G r G x G holds and a G r G implies a G x G . In this article we show that there is a graph G such that a G r G but a G x G . In the case when the graph G doesn t contain two chordless cycles C4 with a common edge the equality a G r G implies a G x G . Corollary the last statement holds for d G - the minimal dimension of the orthonormal representation of the graph G. Let G be a graph with vertex set V G 1 . n and edge set E G . We are interested in studying the functions of the graph G whose values belong to the interval n G x G . Here n G is the size of the largest stable set in G and x G is the smallest number of cliques that cover the vertices of G. It is well known see for example 1 that for some e 0 it is impossible to approximate in polynomial time n G and x G within a factor of ne assuming P NP. We suppose that better approximation could be obtained for narrow classes of graphs determined on the basis of a system of functions of graph G sandwiched between a G and x G . One such function is the well known Lovasz function 0 G 7 which has many alternative definitions. One of them is based on the notion of the orthonormal labeling of the graph. Orthonormal labeling of dimension k of the graph G is a mapping f V G Rfc such that f v 2 1 for all v E V G and f vị f vj 0 if vị Vj e E G . THE ELECTRONIC JOURNAL OF COMBINATORICS 11 2004 N5 1 Let ei E Rfc be a unit vector which is 0 in all .
