Abstract:
A chain is a tree where two vertices have degree $1$ and all others have degree $2$. A propeller is a tree that has one vertex of degree $3$, three vertices of degree $1$, and all other vertices have degree $2$. A proper propeller is a propeller, where vertices of degree one are at equal distances from the vertex of degree $3$. We study the following problem: how to find the number of $3$-colorings of a chain and a proper propeller in the case where the numbers of vertices of each color are given? In both cases, generating functions are presented.