Let B(G) = {X : X ∈ ℝnxn, X = XT , I ≤ X ≤ I + A(G)} and C(G) = {X : X ∈ ℝnxn, 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) = minX∈C(G) rank(X), r +(G) = minX∈B(G) rank(X). We have shown previously that for every graph G, α(G) ≤ r+(G) ≤ χ̄(G) holds and α(G) = r+(G) implies α(G) = χ̄(G). In this article we show that there is a graph G such that α(G) = r(G) but α(G) <χ̄(G). In the case when the graph G doesn’t contain two chordless cycles C4 with a common edge, the equality α(G) = r(G) implies α(G) = χ̄(G). Corollary: the last statement holds for d(G) - the minimal dimension of the orthonormal representation of the graph G.
Original languageEnglish
JournalElectronic Journal of Combinatorics
Issue number1 N
StatePublished - 2004
Externally publishedYes

ID: 5135368