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-2020 |
Files in This Item:
| File | Size | Format | |
|---|---|---|---|
| YU_Alexander_thesis.pdf | 209.04 kB | Adobe PDF | Request a copy |
Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.