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., University of Vermont, Burlington, VT 05401-1455 USA

Send comments to dan.archdeacon@uvm.edu

December 2003