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


Project Description

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 3-colorability 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 3-colorable.  We wish to identify classes of graphs for which the 3-colorability problem is solvable in polynomial time, and classes of graphs for which the 3-colorability problem is solvable in NP-complete 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 3-colorability problem is NP-complete in the class of claw-free graphs.  A claw is a subgraph with the following structure:

Therefore, we will restrict our study to subclasses of claw-free graphs.  One interesting subclass of claw-free graphs is (class, diamond)-free graphs, which has also been shown to be NP-complete (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 claw-free graphs and show whether the 3-colorability problem for the subclasses belongs to P or NP-complete.

 


DIMACS REU