TOPICS
Search

Colin de Verdière Invariant


The Colin de Verdière invariant mu(G) of a nonempty finite simple graph G is the largest nullity of a real symmetric matrix M indexed by its vertices satisfying three conditions. Its off-diagonal entries are negative on edges and zero on nonedges, it has exactly one negative eigenvalue counted with multiplicity, and it has the strong Arnold property. The diagonal entries are unrestricted (Colin de Verdière 1990).

The Colin de Verdière chromatic conjecture relates this invariant to the chromatic number. It differs from maximum nullity, whose defining matrix class does not impose the sign, eigenvalue, and strong Arnold property conditions.


See also

Chromatic Number, Colin de Verdiere Chromatic Conjecture, Maximum Nullity, Strong Arnold Property

Explore with Wolfram|Alpha

References

Colin de Verdière, Y. "Sur un nouvel invariant des graphes et un critère de planarité." J. Combin. Th. Ser. B 50, 11-21, 1990. https://doi.org/10.1016/0095-8956(90)90093-F.

Cite this as:

Weisstein, Eric W. "Colin de Verdière Invariant." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/ColindeVerdiereInvariant.html

Subject classifications