TY - JOUR

T1 - On the functions with values in [alpha(G),(chi)over-bar(G)]

AU - Dobrynin, Pavel

AU - Pliskin, M

AU - Prosolupov, E

PY - 2004/3/22

Y1 - 2004/3/22

N2 - LetB(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)}andC(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.

AB - LetB(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)}andC(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.

KW - CHROMATIC NUMBER

KW - RANK

KW - GRAPH

M3 - статья

VL - 11

JO - Electronic Journal of Combinatorics

JF - Electronic Journal of Combinatorics

SN - 1097-1440

IS - 1

M1 - 5

ER -