- Series
- Graph Theory Seminar
- Time
- Thursday, March 16, 2017 - 3:05pm for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- Rose McCarty – Math, GT
- Organizer
- Robin Thomas
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.