最大度为7且短圈不正常相交的平面图的全染色

发布时间：2020-02-21 07:17

【摘要】：一个图G的k-全染色是指用k种颜色对G的顶点和边进行染色,使得相邻或相关联的元素染不同的颜色.图G的全色数χ_T(G)是使G存在k-全染色的最小整数k.证明了最大度为7且3-圈与5-圈不正常相交的平面图的全色数是8.
【图文】：

，使得Ｍ饱和所有的２－点．由引理３，定义：如果ｕｖ∈Ｍ且ｄ（ｕ）＝２，那么称ｖ是ｕ的２－主点．由引理２和引理３，Ｇ中每一个２－点都有一个２－主点，且只有７－点才能成为２－主点，一个７－点至多只能成为一个２－点的２－主点．引理４［１３］设ｖ是Ｇ的一个７－点且ｎ２（ｖ）≥１，则ｎ４＋（ｖ）≥１．引理５［１１］Ｇ没有（４，４，７－）－面．图１Ｇ的可约构形Ｆｉｇ．１ＲｅｄｕｃｉｂｌｅＣｏｎｆｉｇｕｒａｔｉｏｎｓｏｆＧ引理６［１１］Ｇ不包含图１的５个子图．用·表示的点在原图中没有图示以外的其他邻点．我们将通过欧拉公式和权转移方法导出定理１所需的矛盾．由握手定理∑ｖ∈Ｖｄ（ｖ）＝２Ｅ＝∑ｆ∈Ｆｄ（ｆ）可将连通平面图的欧拉公式Ｖ－Ｅ＋Ｆ＝２改写成∑ｖ∈Ｖ（２ｄ（ｖ）－６）＋∑ｆ∈Ｆ（ｄ（ｆ）－６）＝－１２＜０．首先给Ｇ的顶点ｖ分配初始权ｃｈ（ｖ）＝２ｄ（ｖ）－６，给Ｇ的面ｆ分配初始权ｃｈ（ｆ）＝ｄ（ｆ）－６，则∑ｘ∈Ｖ∪Ｆｃｈ（ｘ）＝－１２．以下将定义一个权转移规则，重新分配点和面的权，记ｃｈ′（ｘ）是重新分配点和面的权后元素ｘ∈Ｖ∪Ｆ的新权，将要证明对每个ｘ∈Ｖ∪Ｆ都有ｃｈ′（ｘ）≥０．而由于权转移过程保持权的总量不变，故０≤∑ｘ∈Ｖ∪Ｆｃｈ′（ｘ）＝∑ｘ∈Ｖ∪Ｆｃｈ

，使得Ｍ饱和所有的２－点．由引理３，定义：如果ｕｖ∈Ｍ且ｄ（ｕ）＝２，那么称ｖ是ｕ的２－主点．由引理２和引理３，Ｇ中每一个２－点都有一个２－主点，且只有７－点才能成为２－主点，一个７－点至多只能成为一个２－点的２－主点．引理４［１３］设ｖ是Ｇ的一个７－点且ｎ２（ｖ）≥１，则ｎ４＋（ｖ）≥１．引理５［１１］Ｇ没有（４，４，７－）－面．图１Ｇ的可约构形Ｆｉｇ．１ＲｅｄｕｃｉｂｌｅＣｏｎｆｉｇｕｒａｔｉｏｎｓｏｆＧ引理６［１１］Ｇ不包含图１的５个子图．用·表示的点在原图中没有图示以外的其他邻点．我们将通过欧拉公式和权转移方法导出定理１所需的矛盾．由握手定理∑ｖ∈Ｖｄ（ｖ）＝２Ｅ＝∑ｆ∈Ｆｄ（ｆ）可将连通平面图的欧拉公式Ｖ－Ｅ＋Ｆ＝２改写成∑ｖ∈Ｖ（２ｄ（ｖ）－６）＋∑ｆ∈Ｆ（ｄ（ｆ）－６）＝－１２＜０．首先给Ｇ的顶点ｖ分配初始权ｃｈ（ｖ）＝２ｄ（ｖ）－６，给Ｇ的面ｆ分配初始权ｃｈ（ｆ）＝ｄ（ｆ）－６，则∑ｘ∈Ｖ∪Ｆｃｈ（ｘ）＝－１２．以下将定义一个权转移规则，重新分配点和面的权，记ｃｈ′（ｘ）是重新分配点和面的权后元素ｘ∈Ｖ∪Ｆ的新权，将要证明对每个ｘ∈Ｖ∪Ｆ都有ｃｈ′（ｘ）≥０．而由于权转移过程保持权的总量不变，，故０≤∑ｘ∈Ｖ∪Ｆｃｈ′（ｘ）＝∑ｘ∈Ｖ∪Ｆｃｈ


本文编号：2581559