On ordering of β-description trees

Huang, Sumin and Kitaev, Sergey (2024) On ordering of β-description trees. Theoretical Computer Science, 982. 114273. ISSN 0304-3975 (https://doi.org/10.1016/j.tcs.2023.114273)

[thumbnail of Huang-Kitaev-TCS-2023-On-ordering-of-beta-description]
Preview
 Text. Filename: Huang_Kitaev_TCS_2023_On_ordering_of_beta_description.pdf
Final Published Version
License: Creative Commons Attribution 4.0 logo
Download (484kB)| Preview

Abstract

Tutte introduced planar maps in the 1960s in connection with what later became the celebrated Four-Color Theorem. A planar map is an embedding of a planar graph in the plane. Description trees, in particular, β-description trees, were introduced by Cori, Jacquard and Schaeffer in 1997, and they give a powerful tool to study planar maps. In this paper we introduce a relation on β-description trees and conjecture that this relation is a total order. Towards solving this conjecture, we provide an embedding of β(a,b)-trees into β(a−t,b+t)-trees for t≤a≤b+t, which is a far-reaching generalization of an unpublished result of Claesson, Kitaev and Steingrímsson on embedding of β(1,0)-trees into β(0,1)-trees that gives a combinatorial proof of the fact that the number of rooted nonseparable planar maps with n+1 edges is more than the number of bicubic planar maps with 3n edges.

CORE (COnnecting REpositories)