Please use this identifier to cite or link to this item: http://arks.princeton.edu/ark:/88435/dsp0112579v719
 Title: List 3-coloring P6-free graphs Authors: Yu, Alexander J Advisors: Chudnovsky, Maria Contributors: Liu, Chun-Hung Department: Mathematics Class Year: 2016 Abstract: The decision problem of list 3-coloring is NP-complete in general. The natural approach to studying this problem is to restrict the problem to specific families of graphs. In this paper, we examine the problem restricted to the family of P6-free graphs. We describe a novel polynomial time algorithm for solving the decision problem in this setting. Extent: 13 pages URI: http://arks.princeton.edu/ark:/88435/dsp0112579v719 Type of Material: Princeton University Senior Theses Language: en_US Appears in Collections: Mathematics, 1934-2016

Files in This Item:
File SizeFormat