Masters Thesis Defense - Matthew Jakubowski

Partial Colorings of Graphs

  • When: Friday, May 2, 12:00pm
  • Where: RI-224A
  • Advisory Committee Chair: Jonathan Cutler
  • Committee Members: Dr. Aihua Li and Dr. Diana Thomas
Abstract: Recently, there has been great interest in counting the
number of homomorphisms from a graph G into a fixed image graph H. For
this thesis, we let H be a complete graph on three vertices with
exactly one looped vertex. Homomorphisms from a graph G to this H
correspond to partial proper two-colorings of the vertices of G. We
are mainly interested in finding which graphs maximize the number of
partial two-colorings given a graph with n vertices and m edges. The
general result is given for all graphs with m+1 at most n as well as
some enumerative results for some very common graphs.