Georgia Institute of Technology College of Sciences

For a graph G, the Colin de Verdière graph parameter mu(G) is the maximum corank of any matrix in a certain family of generalized adjacency matrices of G. Given a non-negative integer t, the family of graphs with mu(G) <= t is minor-closed and therefore has some nice properties. For example, a graph G is planar if and only if mu(G) <= 3. Colin de Verdière conjectured that the chromatic number chi(G) of a graph satisfies chi(G) <= mu(G)+1. For graphs with mu(G) <= 3 this is the Four Color Theorem. We conjecture that if G has at least t vertices and mu(G) <= t, then |E(G)| <= t|V(G)| - (t+1 choose 2). For planar graphs this says |E(G)| <= 3|V(G)|-6. If this conjecture is true, then chi(G) <= 2mu(G). We prove the conjectured edge upper bound for certain classes of graphs: graphs with mu(G) small, graphs with mu(G) close to |V(G)|, chordal graphs, and the complements of chordal graphs.