Mobile version of Hanspub

文章引用说明 更多>> (返回到该文章)

Euler, L. (1752) Elementa doctrinae solidorum. Demonstratio nonnullarum insignium proprietatum. Novi Comment Acad. Sc. Imp. Petropol., 4, 109-160.


  • 标题: 曲面上色临界图点数的上界Upper Bound for the Number of Vertices of Color-Critical Graphs on Surfaces

    作者: 李青青, 晁福刚, 路伟华, 任韩

    关键字: 嵌入, 亏格, 着色, 色临界图Embedding, Genus, Coloring, Color-Critical Graph

    期刊名称: 《Advances in Applied Mathematics》, Vol.3 No.2, 2014-05-13

    摘要: Dirac观察到:对每个固定的曲面S和每个固定的自然数k ≥ 8,曲面S上仅有有限多个k-色临界图。Mohar和Thomassen证明了:对于亏格g ≥ 2的曲面S,曲面S上的7-色临界图的点数少于138(g ‒ 1)。我们借助于Euler公式和Gallai所发展起来的研究色临界图的方法,改进了这个结果,给出了曲面S上的7-色临界图的个数是有限的一个比较简洁的证明。除此以外,我们还给出曲面S上的每一个k-色临界图(k ≥ 7)的点数上界的一个统一的表达式。 Dirac observed that, for each fixed surface and each natural number k ≥ 8, there are only finitely many k-color-critical graphs on S. Mohar and Thomassen proved that for a surface S of genus g ≥ 2, every 7-color-critical graph on S has less than 138(g ‒ 1) vertices. Using Euler formula and the critical-graphs methods of Gallai, we improve this result and give a simple proof that the number of 7-color-critical graphs is finite. We also give unified expression for an upper bound of vertices of k-color-critical graphs (k ≥ 7) on surfaces.