On the function “sandwiched” between α(G) and \overline{χ}(G)

V. Y. Dobrynin^{1}

Submitted: July 18, 1997; Accepted: September 2, 1997

Abstract

A new function of a graph G is presented. Say that a matrix B that is indexed by vertices of G is feasible for G if it is real, symmetric and I ≤ B ≤ I + A(G), where I is the identity matrix and A(G) is the adjacency matrix of G. Let B(G) be the set of all feasible matrices for G, and let \overline{χ}(G) be the smallest number of cliques that cover the vertices of G. We show that

α(G) ≤ min\{ rank(B) |B ∈ B(G)\} ≤ \overline{χ}(G)

and that α(G) = min\{ rank(B) |B ∈ B(G)\} implies α(G) = \overline{χ}(G).

The well known Lovász number ϑ(G) of a graph G [1] is “sandwiched” between the size of the largest stable set in G and the smallest number of cliques that cover the vertices of G

α(G) ≤ ϑ(G) ≤ \overline{χ}(G).

Some alternative definitions of ϑ(G) are introduced in [2,3]. For example,

ϑ(G) = max{ Λ(B) |B is a real positive semidefinite matrix

indexed by vertices of G, B_{vv} = 1 for all v ∈ V (G), B_{uv} = 0 whenever u − v in G},

where Λ(B) is the maximum eigenvalue of B, V (G) — the set of vertices of G, u − v denotes the adjacency of vertices u and v.

Call the matrix B indexed by vertices of G feasible for G if

B is real and symmetric, B_{vv} = 1 for all v ∈ V (G), B_{uv} = 0 whenever u −̸− v in G, 0 ≤ B_{uv} ≤ 1 whenever u − v in G.

Let B(G) be the set of all feasible matrices for G. Then [4]

\overline{χ}(G) = min\{ rank(B) |B ∈ B(G), B = C^{T} C, C ≥ 0\},

Typeset by AMS-TEX

1e-mail address: <vdobr@gamma.niimm.spb.su>

where the inequality denotes componentwise inequality.

The aim of this paper is to study a new function of graph G

min{ rank(B) |B ∈ B(G)}.

Clearly α(G) ≤ min{ rank(B) |B ∈ B(G)}, because every stable set in G with k vertices corresponds to an identity k × k-submatrix of any matrix B ∈ B(G).

Theorem. For all graphs G

α(G) = min{ rank(B) |B ∈ B(G)}

implies α(G) = \overline{χ}(G).

Proof. Let S = \{v_{1}, v_{2}, …, v_{α(G)}\} be the stable set of G, \overline{S} = V (G) \ S and B ∈ B(G) is a matrix such that rank(B) = α(G). We can assume that

B = ( \begin{matrix}I_{α(G)} & X \\ X^{T} & Y \end{matrix} ) ,

where I_{α(G)} is the identity α(G) × α(G)-matrix.

Applying block Gauss elimination, B reduces to the matrix

B′ = ( \begin{matrix}I_{α(G)} & X \\ 0 & Y − X^{T} X \end{matrix} ) .

We have

Y − X^{T} X = 0

or

Y_{uv} − ∑_{w∈S} X_{wu}X_{wv} = 0, u, v ∈ \overline{S}  (1)

since rank(B′) = rank(B) = α(G).

Equation (1) gives us further information about the graph G.

(i) If v ∈ \overline{S} then exists u ∈ S such that u − v. Indeed, Y_{vv} = 1 and X_{wv} ≥ 0 for all w ∈ S. Hence, ∑_{w∈S} X_{wv}^{2} = 1 and X_{uv} > 0 for some u ∈ S.

(ii) If v′, v′′ ∈ \overline{S} and X_{uv′}X_{uv′′} > 0 for some u ∈ S then v′ − v′′. Indeed, if

∑_{w∈S} X_{wv′}X_{wv′′} > 0 then Y_{v′v′′} > 0. Let

V_{u} = \{u\} ∪ \{v|v ∈ \overline{S}, X_{uv} > 0\}

for all u ∈ S and G(V_{u}) be the subgraph induced from G by leaving out all vertices except vertices from V_{u}. We know from (i) and (ii) that G(V_{u}) is a clique and V (G) = ∪_{u∈S}V_{u}. Hence, \overline{χ}(G) = α(G).

Corollary. If \overline{χ}(G) ≤ α(G) + 1 then

\overline{χ}(G) = min\{ rank(B) |B ∈ B(G)\}.

For example, consider the Petersen graph G. We have α(G) = ϑ(G) = 4, \overline{χ}(G) = 5. Hence, min{ rank(B) |B ∈ B(G)} = 5.

There is a graph G such that

α(G) < min\{ rank(B) |B ∈ B(G)\} < \overline{χ}(G).

Let V (G) = 2^{{1,2,3,4,5,6}} and u − v iff 2 ≤ |(u \ v) ∪ (v \ u)| ≤ 5 for all u, v ∈ V (G). Then [5] χ(G) = 32 and rank(A(G)) = 29 where A(G) is the adjacency matrix of G. Then \overline{χ}(\overline{G}) = 32 and

rank(I + A(\overline{G})) = rank(J − A(G)) ≤ 1 + rank(A(G)) = 30,

where J is all 1’s.

Notice that I + A(\overline{G}) ∈ B(\overline{G}). Therefore

min\{ rank(B) |B ∈ B(\overline{G})\} < \overline{χ}(\overline{G})

and

α(\overline{G}) < min\{ rank(B) |B ∈ B(\overline{G})\}

by theorem.

Acknowledgement.

The author is grateful to the anonymous referee for valuable remarks.

References

1. L. Lovász, “On the Shannon capacity of a graph”, IEEE Transactions on Information Theory IT–25 (1979), 1–7.

2. Martin Grötschel, László Lovász, and Alexander Schrijver, Geometric Algorithms and Combinatorial Optimization (Springer-Verlag, 1988).

3. Donald E.Knuth, “The Sandwich Theorem”, Electronic J. Combinatorics 1, A1 (1994), 48 pp.

4. V.Y.Dobrynin, “The chromatic number of a graph and rank of matrix associated with it”, Vestnik Sankt-Peterburgskogo Universiteta, Ser.1, Issue 2, Vol.15 (1995), 120–122.

5. N.Alon, P.D.Seymour. “A counterexample to the rank-coloring conjecture”, Journal of Graph Theory 13 (1989), 523–525.