Dominating sets in graphs with no long induced paths

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.