REU at Rutgers University
Welcome to Sam Nelson's REU Website
Student: 
Sam Nelson 
School: 
Bucknell University 
Email Address: 
snelson@bucknell.edu 
Advisor: 
Prof. Vadim Lozin, Rutgers University 
Research Area: 
Graph Theory 
Graph theory is the study of graphs and properties associated with them. Graphs are a collection of vertices, connected by edges. Because graphs can model many real world scenarios, it is important to analyze different properties and algorithms associated with them. We are interested in the 3colorability problem; that is, assigning each vertex a color (from a set of 3 colors) such that no two adjacent vertices receive the same color. In other words, if a mapping exists from set {0,1,2} to each vertex in the graph such that no two adjacent vertices receive the same number, then the graph is said to be 3colorable. We wish to identify classes of graphs for which the 3colorability problem is solvable in polynomial time, and classes of graphs for which the 3colorability problem is solvable in NPcomplete time. Furthermore, we wish to give coloring algorithms for these graphs and prove their time complexity. Classes of Graphs It has been shown that the 3colorability problem is NPcomplete in the class of clawfree graphs. A claw is a subgraph with the following structure: Therefore, we will restrict our study to subclasses of clawfree graphs. One interesting subclass of clawfree graphs is (class, diamond)free graphs, which has also been shown to be NPcomplete (if the maximum vertex degree is at most four). A diamond is a subgraph with the following structure: This summer we hope to identify different subclasses of clawfree graphs and show whether the 3colorability problem for the subclasses belongs to P or NPcomplete.
