English

运筹学学报 ›› 2015, Vol. 19 ›› Issue (1): 125-130.

• 运筹学 • 上一篇    

嵌入曲面的特殊图的边染色

孙林1,2,*, 罗朝阳1,2   

  1. 1. 昌吉学院数学系, 新疆昌吉 830100; 2. 山东大学数学学院, 济南 250100
  • 收稿日期:2014-07-18 出版日期:2015-03-15 发布日期:2015-03-15
  • 通讯作者: 孙林 E-mail:fiona\_sl@163.com
  • 基金资助:

    新疆自治区高校科研计划项目(Nos. XJEDU2014S067, XJEDU2014I046)

Edge colourings of embedded special graphs

SUN Lin1,2,*, LUO Zhaoyang1,2   

  1. 1. Department of Mathematics, Changji College, Changji 830100, Xinjiang, China; 2. School of Mathematics, Shandong University, Jinan 250100, China
  • Received:2014-07-18 Online:2015-03-15 Published:2015-03-15

PDF

563

摘要： 设图\,$G$\,是嵌入到欧拉示性数\,$\chi(\Sigma)\geq 0$\,的曲面\,$\Sigma$\,上的图, $\chi'(G)$\,和\,$\Delta(G)$\,分别表示图\,$G$\,的边色数和最大度. 如果\,$\Delta(G)\geq 4$\,且\,$G$\,满足以下条件: (1)\,图$G$中的任意两个三角形$T_1$, $T_2$的距离至少是$2$; (2)\,图\,$G$\,中\,$i$-圈和\,$j$-圈的距离至少是\,$1$, $i,j\in\{3,4\}$; (3)\,图\,$G$\,中没有\,$5$-圈, 则有\,$\Delta(G)=\chi'(G)$.

关键词: 欧拉示性数, 圈, 边色数, 放电法

Abstract: Let $G$ be a graph embedded on a surface $\Sigma$ of Euler characteristic $\chi(\Sigma)\!\geq\!0$.\\ $\chi'(G)$ and $\Delta(G)$ denote the chromatic index and the maximum degree of $G$, respectively. The paper shows that $\Delta(G)=\chi'(G)$ if the graph $G$ with $\Delta(G)\geq 4$ satisfies the following properties: (1) any two triangles with distance at least two; (2) any $i$-cycle and $j$-cycle with distance at least one, $i,j\in\{3,4\}$; (3) $G$ contains no $5$-cycles.

Key words: Euler characteristic, cycles, the chromatic index, discharging method

中图分类号: