Skip navigation
Please use this identifier to cite or link to this item:
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
Type of Material: Princeton University Senior Theses
Language: en_US
Appears in Collections:Mathematics, 1934-2020

Files in This Item:
File SizeFormat 
YU_Alexander_thesis.pdf209.04 kBAdobe PDF    Request a copy

Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.