On $3$-coloring of chains and propellers
Fundamentalʹnaâ i prikladnaâ matematika, Tome 25 (2024) no. 2, pp. 177-181
Citer cet article
Voir la notice de l'article provenant de la source Math-Net.Ru
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.
[1] Lando S. K., Vvedenie v diskretnuyu matematiku, MTsNMO, M., 2012
[2] Kharari F., Teoriya grafov, URSS, M., 2006