# Bijective Enumeration of Bicolored Maps of Given Vertex Degree Distribution

Abstract : We derive a new formula for the number of factorizations of a full cycle into an ordered product of two permutations of given cycle types. For the first time, a purely combinatorial argument involving a bijective description of bicolored maps of specified vertex degree distribution is used. All the previous results in the field rely either partially or totally on a character theoretic approach. The combinatorial proof relies on a new bijection extending the one in [G. Schaeffer and E. Vassilieva. $\textit{J. Comb. Theory Ser. A}$, 115(6):903―924, 2008] that focused only on the number of cycles. As a salient ingredient, we introduce the notion of thorn trees of given vertex degree distribution which are recursive planar objects allowing simple description of maps of arbitrary genus. \par
Keywords :
Document type :
Conference papers
Domain :

Cited literature [10 references]

https://hal.inria.fr/hal-01185374
Contributor : Coordination Episciences Iam <>
Submitted on : Thursday, August 20, 2015 - 11:06:24 AM
Last modification on : Thursday, March 5, 2020 - 6:31:07 PM
Long-term archiving on: : Wednesday, April 26, 2017 - 10:08:54 AM

### File

dmAK0155.pdf
Publisher files allowed on an open archive

### Identifiers

• HAL Id : hal-01185374, version 1

### Citation

Alejandro Morales, Ekaterina Vassilieva. Bijective Enumeration of Bicolored Maps of Given Vertex Degree Distribution. 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009), 2009, Hagenberg, Austria. pp.661-672. ⟨hal-01185374⟩

Record views