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.