Princeton University Library Catalog

List 3-coloring P6-free graphs

Author/​Artist:
Yu, Alexander J [Browse]
Format:
Senior thesis
Language:
English
Advisor(s):
Chudnovsky, Maria [Browse]
Contributor(s):
Liu, Chun-Hung [Browse]
Department:
Princeton University. Department of Mathematics [Browse]
Class year:
2016
Description:
13 pages
Summary note:
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.