**Colin de Verdiere's mu
parameter**

Colin de Verdiere [C] introduced a new parameter mu for graphs. Its definition is a
bit difficult.

Let G be a graph on n vertices. Let mu(G) denote the maximum
multiplicity of the second eigenvalue taken over among all symmetric n x n matricies M such that a) M(i,j) is negative if ij is an edge and is 0 otherwise, b) M has exactly one negative
eigenvalue, and c) M
satisfies the strong Arnold hypothesis.

Colin de Verdiere showed that mu
was minor-monotone. He also showed that mu(G) was at most 2 for
outer-planar graphs and at
most 3 for planar graphs. He conjectures:

Conjecture: mu(G) is at least the chromatic number minus 1.

If this conjecture is true, it would imply the four-color theorem.
The following is proposed (by Robin Thomas?) as a characterization of
graphs with mu at most 4.

Conjecture: Is mu(G) at most 4 if and only if G can be embedded in 3-space such that every
cycle of G bounds a disk
disjoint from the graph?

For more details see [L], [H], and [HLS].

**References:**

[C] Colin de Verdiere, Sur un vouvel invariant des graphes et un
critere de planarite (French), J.
Combin. Theory Ser. B 50-1
(1990) 11-21

[L] L. Lovasz, Steinitz representations of polyhedra and the Colin
de Verdiere number, J. Combin.
Theory Ser. B 82 (2001)
223-236

[H] H. van der Holst, A short proof of the planarity
characterization of Colin de Verdière, J. Combin Theory Ser B 65-2 (1995) 269-272

[HLS] H. van der Holst, L Lovasz, and A. Schrijver, The Colin de
Verdiere graph parameter, Graph
theory and combinatorial biology (Balatonlelle, 1996) Bolyai Soc. Math.
Stud, 7, Janos Bolya
math. Soc. Budapest (1999) 29-85

[RST] N. Robertson, P.D. Seymour, and R. Thomas, A survey of
linkless embeddings, Contemporary
Mathematics 147 (1993)

Submitted by: Dan Archdeacon, Dept. of Math.
and Stat.,

Send comments to *dan.archdeacon@uvm.edu*

December 2003