我所初识的高等图论(Ⅳ):二重图上Euler回

系统地介绍了作者早期在图的上可嵌入性和最大亏格方面所进行的开创性的工作.然后把二重图、标准Euler回、叉帽与手柄、上可嵌入性与最大亏格等归结为,由他所成形的多面形理论体系.在此基础上,特别反映了国内在这一领域的独特研究进展,包括理论层面和实际应用层面.

边覆盖染色问题的有效算法

设G=(V,E)是一个重图.若边子集F的导出子图是G的一个生成子图,则称F为G的一个边覆盖.G的边覆盖色数ξ(G)是使得G可划分的最大不交边覆盖数.用δ(G)表示G的最小阶,令ρ(G)=min{2|?(U)|/(|U|+1):U?V(G),|U|≥3为奇数},其中?(U)表示至少有一个端点在U中的边集合.显然,ξ(G)≤min{δ(G),「ρ(G)」}.本文证明了,对系列平行重图和近似二部重图,此处等号成立,并且通过证明得到计算这两类重图的边覆盖色数的多项式时间算法.