论文标题
嵌入式图及其Tutte多项式的类型
Types of embedded graphs and their Tutte polynomials
论文作者
论文摘要
我们采用基本和系统的方法来将Tutte多项式扩展到嵌入式图的设置。当考虑表面图上的删除和收缩操作时，自然会出现四个嵌入图的概念。我们用彩色色带图对每个类别进行描述。然后，我们为每个类别确定一个通用的删除 - 接收不变（即“ Tutte多项式”）。我们将它们与文献中的多项式相关联，包括Bollobás-riordan，Krushkal和Las Vergnas多项式，并为每个人提供了状态和二元关系，二元关系，Deleton-Contraction关系以及准树的扩展。
We take an elementary and systematic approach to the problem of extending the Tutte polynomial to the setting of embedded graphs. Four notions of embedded graphs arise naturally when considering deletion and contraction operations on graphs on surfaces. We give a description of each class in terms of coloured ribbon graphs. We then identify a universal deletion-contraction invariant (i.e., a `Tutte polynomial') for each class. We relate these to graph polynomials in the literature, including the Bollobás--Riordan, Krushkal, and Las Vergnas polynomials, and give state-sum formulations, duality relations, deleton-contraction relations, and quasi-tree expansions for each of them.
