In 1996, Matheson and Tarjan conjectured that any n-vertex triangulation with n sufficiently large has a dominating set of size at most n/4. We prove this for graphs of maximum degree 6.

All terminology will be introduced from scratch, with plenty of examples, so this talk should be suitable for undergraduates. However, if you just can't wait: A triangulation is a graph drawn on the plane so that every face is a triangle. A subset of vertices S of a graph G is a dominating set if every vertex of G is either (i) in S or (ii) adjacent to some vertex of S.

This is joint work with Erika L. C. King from Hobart and William Smith Colleges.