Orthogonal representations over finite fields and the chromatic number of graphs

We study the relationship between the minimum dimension of an orthogonal representation of a graph over a finite field and the chromatic number of its complement. It turns out that for some classes of matrices defined by a graph the 3-colorability problem is equivalent to deciding whether the class defined by the graph contains a matrix of rank 3 or not. This implies the NP-hardness of determining the minimum rank of a matrix in such a class. Finally we give for any class of matrices defined by a graph that is interesting in this respect a reduction of the 3-colorability problem to the problem of deciding whether or not this class contains a matrix of rank equal to three.The author is financially supported by the Cooperation Centre Tilburg and Eindhoven Universities.