On the rank of a matrix associated with a graph Original Research Article

Let X be a real symmetric matrix indexed by the vertices of a graph G such that all its diagonal entries are 1, Xij=0 whenever vertices i,j are non-adjacent and |Xij|⩽1 for all other entries of X. Let r(G) be the minimum possible rank of the matrix X. Then α(G)⩽r(G)⩽χ̄(G). It is well known that there is no upper bound on χ̄(G) in terms of α(G). For every natural k⩾2 there exists graph G such that α(G)=2 and χ̄(G)=k. So it is interesting to find out whether there is an upper bound on χ̄(G) in terms of r(G). It is proved here that r(G)=i iff d(G)=i for i⩽3. Here d(G) is the minimum dimension of the orthonormal labellings of G. Hence, if r(G)⩽3 then χ̄(G)⩽2r(G)−1.