关于图的上可嵌入性的一个注记

任韩和李刚在图的最大亏格综述一文"Survey of maximum genus of graphs" J East China NormUniv Natur Sci, Sep. 2010, No. 5, 1-13] 中,全面地阐述了近30 年来关于图的最大亏格及其相关问题所取得的进展,并提出了如下两个猜想:
猜想1 设G 为简单连通图, 且G 的每条边含在一个三角形K₃ 中, 则G 是上可嵌入的.
猜想2 设c 为任意的正数, 则存在一个自然数N(c), 使得对每一个图G, 若G 的点数n ≥ N(c), 且最小度δ(G) ≥ cn, 则G 是上可嵌入的.
本文的主要工作是否定上述两个猜想, 同时探讨上述猜想成立的条件且得了一些新结果, 并提出有关进一步研究的问题.

A note on the upper embeddability of graphs

In ＂Survey of maximum genus of graphs＂ J East China Norm Univ Natur Sci, Sep. 2010, No. 5, 1-13], Ren and Li reviewed research developments on maximum genus of graphs in graph embedding theory since 1971, and presented the following two conjectures： Conjecture 1, Let G be a simple connected graph such that each edge is contained in a triangle Ka. Then G is upper-embeddable. Conjecture 2. Let c be an arbitrary positive number. Then, there exists a natural number N（c） such that for every graph G of order n ≥ N（c） and minimum degree δ（G） ≥ cn, G is upper-embeddable. In this paper, we negate the above two conjectures, and discuss the condition for which the above conjectures is true and obtain some new results. Finally, we present several research problems that would be developed in the future.