Please use this identifier to cite or link to this item:
http://arks.princeton.edu/ark:/88435/dsp0112579v719Full metadata record
| DC Field | Value | Language |
|---|---|---|
| dc.contributor | Liu, Chun-Hung | - |
| dc.contributor.advisor | Chudnovsky, Maria | - |
| dc.contributor.author | Yu, Alexander J | - |
| dc.date.accessioned | 2016-07-11T15:56:37Z | - |
| dc.date.available | 2016-07-11T15:56:37Z | - |
| dc.date.created | 2016-05-02 | - |
| dc.date.issued | 2016-07-11 | - |
| dc.identifier.uri | http://arks.princeton.edu/ark:/88435/dsp0112579v719 | - |
| dc.description.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. | en_US |
| dc.format.extent | 13 pages | * |
| dc.language.iso | en_US | en_US |
| dc.title | List 3-coloring P6-free graphs | en_US |
| dc.type | Princeton University Senior Theses | - |
| pu.date.classyear | 2016 | en_US |
| pu.department | Mathematics | en_US |
| pu.pdf.coverpage | SeniorThesisCoverPage | - |
| 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.