On the Colin de Verdière number of graphs

Let μ(G) and ω(G) be the Colin de Verdière and clique numbers of a graph G, respectively. It is well-known that μ(G)⩾ω(G)-1 for all graphs. Our main results include μ(G)⩽ω(G) for all chordal graphs; μ(G)⩽tw(G)+1 for all graphs (where tw is the tree-width), and a characterization of those split (⊆ chordal) graphs for which μ(G)=ω(G). The bound μ(G)⩽tw(G)+1 improves a result of Colin de Verdière by a factor of 2.