\(\{P_r\}\)-free Colorings of Sierpinski-like Graphs

Abstract

Suppose \(\{P_r\}\) is a nonempty family of paths for \(r \geq 3\), where \(P_r\) is a path on \(r\) vertices. An \(r\)-coloring of a graph \(G\) is said to be \(\{P_r\}\)-free if \(G\) contains no 2-colored subgraph isomorphic to any path \(P_r\) in \(\{P_r\}\). The minimum \(k\) such that \(G\) has a \(\{P_r\}\)-free coloring using \(k\) colors is called the \(\{P_r\}\)-free chromatic number of \(G\) and is denoted by \(\chi_{\{P_r\}}(G)\). If the family \(\{P_r\}\) consists of a single graph \(P_r\), then we use \(\chi_{P_r}(G)\). In this paper, \(\{P_r\}\)-free colorings of Sierpiński-like graphs are considered. In particular, \(\chi_{P_3}(S_n)\), \(\chi_{P_4}(S_n)\), \(\chi_{P_4}(S(n, k))\), \(\chi_{P_3}(S^{++}(n, k))\), and \(\chi_{P_4}(S^{++}(n, k))\) are determined.