A note on the upper embeddability of graphs
Yuanqiu Huang, Ting Guo · Scientia Sinica Mathematica · 2012
In Survey of maximum genus of [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 K 3 . 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.