Abstract
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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
R. L. Brooks: On colouring the nodes of a network,Proceedings of the Cambridge Philosophical Society,37 (1941), 194–197.
A. E. Brouwer, A. M. Cohen, andA. Neumaier:Distance-Regular Graphs, Ergebnisse der Mathematik 3.18, Springer, Heidelberg (1989).
S. Even:Graph Algorithms, Pitman, (1979).
M. R. Garey, D. S. Johnson, andL. J. Stockmeyer: Some NP-Complete Graph Problems,Theor. Comput. Sci.,1 (1976), 237–267.
M. R. Garey, andD. S. Johnson: The Complexity of Near-Optimal Graph Coloring,J. ACM.,23 (1976), 43–49.
M. R. Garey, andD. S. Johnson:Computers and Intractability: A Guide to the Theory of NP-completeness, Freeman, San Francisco, (1979).
M. Grötchel, L. Lovász, andA. Schrijver: The ellipsoid method and its consequences in combinatorial optimization,Combinatorica,1 (2) (1981), 169–197.
W. Haemers: On the problems of Lovász concerning the Shannon capacity of a graph,IEEE Trans. Inform. Theory,25 (1979), 231–232.
W. Haemers: An upper bound for the Shannon capacity of a graph,Colloqua Mathematica Societatis János Bolyai,25, Algebraic Methods in Graph Theory, Szeged (Hungary), (1978), 267–272.
D. Hershkowitz, andH. Schneider: Ranks of zero patterns and sign patterns, preprint, (1991).
A. J. Hoffman: On eigenvalues and colorings of graphs, in B. Harris, Ed.,Graph Theory and its applications, New York and London: Academic, (1970), 79–91.
D. E. Knuth: The Sandwich Theorem,Electronic J. Comb.,1 (1994), #A1.
L. Lovász: On the Shannon capacity of a graph,IEEE Trans. Inform. Theory,25 (1979), 1–7.
L. Lovász: An Algorithmic Theory of Numbers, Graphs and Convexity,CBMS Regional Conference Series in Applied Mathematics, SIAM, (1986) §3.2.
L. Lovász, M. Saks, andA. Schrijver: Orthogonal Representations and Connectivity of Graphs,Linear Algebra Appl.,114/115 (1989), 439–454.
C. H. Papadimitriou:Computational Complexity, Addison-Wesley Publ. Co., (1994).
R. Peeters:Ranks and Structure of Graphs, dissertation, Tilburg University, (1995).
A. A. Razborov: Applications of matrix methods to the theory of lower bounds in computational complexity,Combinatorica,10 (1) (1990), 81–93.
A. Schrijver: A comparison of the Delsarte and Lovász bounds,IEEE Trans. Inform. Theory,25 (1979), 425–429.
C. E. Shannon: The zero-error capacity of a noisy channel,IRE Trans. Inform. Theory,3 (1956), 3–15.
Author information
Authors and Affiliations
Additional information
The author is financially supported by the Cooperation Centre Tilburg and Eindhoven Universities.