$\{P_r\}$-free Colorings of Sierpinski-like Graphs

Abstract

Suppose $\{P_r\}$ is a nonempty family of paths for $r\ge 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.