RUS  ENG
Full version
JOURNALS // Fundamentalnaya i Prikladnaya Matematika // Archive

Fundam. Prikl. Mat., 2024 Volume 25, Issue 2, Pages 177–181 (Mi fpm1978)

On $3$-coloring of chains and propellers

Yu. Yu. Kochetkov

Moscow Institute of Electronics and Mathematics — Higher School of Economics

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.

UDC: 519.17



© Steklov Math. Inst. of RAS, 2025