9:30 a.m. | Registration and Breakfast |

10:00 a.m. | Pallavi Jayawant: Discrete versions of topological theorems |

11:00 a.m. | Break |

11:30 a.m. | Martin Kochol: Counterexample to the conjecture of Grunbaum |

12:30 p.m. | Lunch |

2:00 p.m. | Joan Hutchinson: Color Extension Theorems for graphs with excluded minors. |

3:00 p.m. | Break |

3:15 p.m. | Mark Ellingham: Tricks with transition graphs |

4:15 p.m. | Break |

4:30 p.m. | Diane Souvaine: Points, Obstacles, Spanning-Trees, and Matchings |

**Title:** Tricks with transition graphs

**Abstract: **Transition graphs are an algebraic way of constructing embeddings
of graphs in surfaces. They are equivalent to embedded voltage graphs but are
more convenient in certain situations. We discuss how transition graphs can
be used to construct embeddings of complete bipartite graphs with very specific
properties. This allows us to construct minimum genus embeddings of complete
tripartite graphs and other related graph families. We discuss some recent
applications. (Joint work with Chris Stephens and Xiaoya Zha, Middle Tennessee
State University)

**Title:** Color Extension
Theorems for graphs with excluded minors.

**Abstract:** We build on a striking theorem
of M.O. Albertson: Let *P* be a set
of vertices of a graph *G* with chromatic number *r*. Then any
(*r*+1)-coloring of
*P* extends to an (*r*+1)-coloring of *G* provided the
vertices of *P* are at mutual
distance at least 4. In addition the parameters 4 and *r*+1 are best
possible. There is a similar extension theorem [A, H, E.H. Moore] when bipartite
subgraphs of *G* are each precolored with two colors, chosen from a
set of *r*+2 colors,
provided the bipartite subgraphs are suitably far apart. But more is true (meaning
fewer colors are needed) when *G* is a planar graph or *G* is
*K*_{5}-minor-free or *G* is K_{4}-minor free.
By the Four Color Theorem and by proven cases of Hadwiger's Conjecture, we
know that those classes of graphs can be 4-, 4-, and 3-colored respectively.
Albertson's theorem gives us a color extension theorem when separated vertices
are precolored, but what happens when bipartite subgraphs are precolored, each
with two colors taken from a restricted set of colors? How large must the pool
of colors be to allow for an extension, and how far apart must the bipartite
components be? We'll survey results of A, H, M and recent work of A. Pruchnewski
and M. Voigt, including results when list-colorings are considered.

**Title:** Discrete versions of topological theorems

**Abstract:** Tucker's Lemma is the discrete
version of the Borsuk-Ulam theorem from topology about continuous functions
on the sphere. Tucker's Lemma is a statement about labellings of triangulations
of the sphere and it was proven in its full generality in 2006. Yang's theorem
is a generalization of the Borsuk-Ulam theorem and Dyson's theorem is a special
case of Yang's theorem about real valued functions on the sphere. I will
discuss the Borsuk-Ulam theorem and Tucker's lemma and some of their applications.
I will then present a combinatorial analog of Dyson's theorem and show the
equivalence of the analog to Dyson's theorem. I will end with a discussion
of possibilities to extend this work to obtain a discrete version of Yang's
theorem. This is joint work with Peter Wong.

**Title: **Counterexample to the conjecture of Grunbaum

**Abstract:** By a classical
result of Tait, the four color theorem is equivalent with the statement that
each 2-edge-connected 3-regular planar graph has a 3-edge-coloring. An embedding
of a graph in a surface is called polyhedral if its dual has no multiple edges
and loops. A conjecture of Grunbaum, presented in 1968, states that each 3-regular
graph with a polyhedral embedding in an orientable surface has a 3-edge-coloring.
With respect to the result of Tait, it aims to generalize the four color theorem
for any orientable surface. We present a negative solution of this conjecture,
showing that for each orientable surface of genus at least 5, there exists
a 3-regular non 3-edge-colorable graph with a polyhedral embedding in the surface.

**Title:** Points, Obstacles, Spanning-Trees, and Matchings

**Abstract:** Given *m* points (sites)
and *n* obstacles (barriers)
in the plane, what is the cost of the minimum spanning tree, where the cost
is proportional to the number of intersections (crossings) between tree edges
and barriers? A set of *n* disjoint line segments in the plane represents
a matching of the *m *= 2*n* endpoints. Is there always a compatible
(non-crossing) disjoint matching? We give some partial results, and discuss
the role of convex partitions of the plane in tackling these and related problems.

Joint work with C. Aichholzer, N. Benbernou, S. Bereg, E. Demaine, M. Demaine, A. Dumitrescu, A. Garcia, M. Hoffmann, C. Huemer, F. Hurtado, M. Ishaque, M. Kano, D. Krumme, A. Marquez, D. Rappaport, E. Rafalin, S. Smorodinsky, C. Toth, J. Urrutia, and D. Wood.