Please use this identifier to cite or link to this item: http://arks.princeton.edu/ark:/88435/dsp01jw827f42s
 Title: Dominating sets in graphs with no long induced paths Authors: Shi, Jessica Advisors: Liu, Chun-HungChudnovsky, Maria Department: Mathematics Certificate Program: Applications of Computing Program Class Year: 2018 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. URI: http://arks.princeton.edu/ark:/88435/dsp01jw827f42s Type of Material: Princeton University Senior Theses Language: en Appears in Collections: Mathematics, 1934-2020