Let

B(G) = {X : X is an element of R-nxn, X = X-T, I less than or equal to X less than or equal to I + A(G)}

and

C(G) = {X : X is an element of R-nxn, X = X-T, I - A(G) less than or equal to X less than or equal to 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) = min(Xis an element ofc(G)) rank(X), r(+)(G) = min(Xis an element ofB(G)) rank(X). We have shown previously that for every graph G, alpha(G) less than or equal to r(+)(G) less than or equal to (χ) over bar (G) holds and alpha(G) = r(+)(G) implies alpha(G) = (χ) over bar (G). In this article we show that there is a graph G such that alpha(G) = r(G) but alpha(G) <(G). In the case when the graph G doesn't contain two chordless cycles C-4 with a common edge, the equality alpha(G) = r(G) implies alpha(G) = (χ) over bar (G). Corollary: the last statement holds for d(G) - the minimal dimension of the orthonormal representation of the graph G.

Original languageEnglish
Article number5
Number of pages5
JournalElectronic Journal of Combinatorics
Volume11
Issue number1
StatePublished - 22 Mar 2004

    Research areas

  • CHROMATIC NUMBER, RANK, GRAPH

ID: 36371825