RUS  ENG
Full version
JOURNALS // Trudy Instituta Matematiki i Mekhaniki UrO RAN // Archive

Trudy Inst. Mat. i Mekh. UrO RAN, 2016 Volume 22, Number 1, Pages 257–262 (Mi timm1278)

This article is cited in 1 paper

On graphs with vertices of two colors and groups with 3-transpositions

A. I. Sozutov, I. O. Aleksandrova

Institute of Mathematics and Computer Science, Siberian Federal University, Krasnoyarsk

Abstract: We consider labeled undirected graphs without loops or multiple edges with vertices of two colors. A coloring of a graph $\Gamma_n$ is called odd-connected if the removal of vertices of the first color produces an odd number of connected components. A general formula for the number $t_n$ of odd-connected colorings is found for certain families of embedded graphs $\Gamma_n$. The formula depends on two parameters. In the cases where two graphs in a family can be interpreted as Coxeter graphs for certain groups with 3-transpositions, specific formulas for the numbers $t_n$ are found.

Keywords: labeled graph, graph coloring, generating function, Ñoxeter graph, group with 3-transpositions.

UDC: 512.54, 519.17

Received: 27.08.2015



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025