Please use this identifier to cite or link to this item:
http://arks.princeton.edu/ark:/88435/dsp01jw827f42s
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.advisor | Liu, Chun-Hung | - |
dc.contributor.advisor | Chudnovsky, Maria | - |
dc.contributor.author | Shi, Jessica | - |
dc.date.accessioned | 2018-08-20T17:46:22Z | - |
dc.date.available | 2018-08-20T17:46:22Z | - |
dc.date.created | 2018-04-30 | - |
dc.date.issued | 2018-08-20 | - |
dc.identifier.uri | http://arks.princeton.edu/ark:/88435/dsp01jw827f42s | - |
dc.description.abstract | 3-coloring is a classically difficult problem, and as such, it is of interest to consider the computational complexity of 3-coloring restricted to certain classes of graphs. \(P_t\)-free graphs are of particular interest, and the problem of 3-coloring \(P_8\)-free graphs remains open. One way to prove that 3-coloring graph class \(\mathcal{G}\) is polynomial is by showing that for all \(G \in \mathcal{G}\), there exists a constant bounded dominating set in \(G\); that is to \(G\) contains a dominating set \(S\) such that \(|S| \leq K_\mathcal{G}\) for constant \(K_\mathcal{G}\). In this paper, we prove that there exist constant bounded dominating sets in subclasses of \(P_t\)-free graphs. Specifically, we prove that excepting certain reducible configurations which can be disregarded in the context of 3-coloring, there exist constant bounded dominating sets in \(\{P_6, \textrm{triangle}\}\)-free and \(\{P_7, \textrm{triangle}\}\)-free graphs. We also provide a semi-automatic proof for the latter case, due to the algorithmic nature of the proof. | en_US |
dc.format.mimetype | application/pdf | - |
dc.language.iso | en | en_US |
dc.title | Dominating sets in graphs with no long induced paths | en_US |
dc.type | Princeton University Senior Theses | - |
pu.date.classyear | 2018 | en_US |
pu.department | Mathematics | en_US |
pu.pdf.coverpage | SeniorThesisCoverPage | - |
pu.contributor.authorid | 961070654 | - |
pu.certificate | Applications of Computing Program | en_US |
Appears in Collections: | Mathematics, 1934-2020 |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
SHI-JESSICA-THESIS.pdf | 366.51 kB | Adobe PDF | Request a copy |
Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.