平面图的多项式与着色

韩友发， 亢云凤， 董 婷

(辽宁师范大学 数学学院， 辽宁 大连 116029)

平面图的多项式与着色

韩友发， 亢云凤， 董 婷

(辽宁师范大学 数学学院， 辽宁 大连 116029)

研究平面剖分图的着色性质，通过讨论图的色多项式的零点问题，分析对图的着色保证相邻的两个区域着不同颜色的最少方法数目，进而给出了平面剖分图的着色方法数目的重要性质.主要研究方法是对平面图的着色提供了一个新的研究渠道，即通过色多项式计算，得出平面剖分前后的着色数目，进而再计算球面剖分图的着色数目.首先，研究“具有一条公共边的两个区域Gn和Gm，及广义剖分图”的着色问题；其次，研究“简单正多面体及球面的三角剖分图”的着色问题.

平面图；色多项式；广义剖分；三角剖分

纽结理论是20世纪以来作为拓扑学的一个重要部分而发展起来的.而且在很多领域得到了应用，进而纽结理论成了拓扑学中引人入胜的一支，它在数学中的重要性日渐上升.1928年由美国数学家亚历山大[1]发现了亚历山大多项式，但是该多项式不能区分纽结和它的镜面像，也就是它们相同的亚历山大多项式.经过50多年，1984年新西兰数学家琼斯[2]找到纽结新的一个多项式不变量能够区分某些亚历山大多项式不能区分的纽结.很快，许多科学家发现纽结理论和许多科学领域都有联系,数学家考夫曼[3]试图用图式方法来探究纽结不变量，而且发现纽结理论与图论有密切的联系，即纽结的投影图与平面图是一一对应的.进而在图论上来探究纽结的交叉点的符号问题，这样就涉及在平面图上的着色问题.平面图的着色问题的研究来源于图论中的着色理论.塔特多项式和方括号多项式是纽结理论和图论的基本关系的主要桥梁，尤其是塔特多项式及与色多项式之间的关系[4-5]对着色问题的研究具有重大的意义.同时，纽结理论在统计力学、生物DNA分子重组等领域都有着广泛的应用[6-8].笔者就是在分析研究这些成果的基础上，重点研究图及剖分图的着色问题.

1 预备知识

1.1 图论中的一些定义

定义1.1一个图是一个偶对V,E:

(1)V是一个集合，其中的元素称为顶点.

(2)E是无序积V×V中的一个子集合，其中的元素称为边；集合V×V中的元素可在E中出现不止一次.

定义1.2起点和终点相同的路径称为闭路径，闭路又称为圈.长为k(k即是边长的个数)的圈称为k-圈,k为偶数时称为偶圈，k为奇数时，称为奇圈.

定义1.3图G称为多重图，如果G中有两个顶点之间有多重边或有一个顶点带一个环.

定义1.4平面图G的对偶图G*定义如下：G中每一个面f内取一点作G*的一个顶点f*，G*中的f*、g*相连接e*的充要条件是f*，g*在G中对应的面f,g含公共边e，且使e和e*相交.

定义1.5平面图G的k-面着色是k种颜色在G的面上的一个分配，称面着色的平面图为k-面可着色.使G为k-面可着色的最小的k称为G的面色数，记为x*G.显然，对任意平面图G，都有x*G=xG*.

1.2 图的双色多项式

首先介绍图的双色多项式Z(G)[3]，它有两个变量q和v，满足下面3个条件：

(1)Z(•)=q;

例

(1)Z()=Z(•)+vZ(•)=q+vq;

P(G)有下列性质：

引理1.1[5]在双色多项式Z(q,v)中，当v=-1时，双色多项式特殊化为色多项式P(G).P(G)表示对图G的顶点用q种颜色着色并保证相邻的两个顶点不同色的着色的方法数目.

引理1.2[5]如果图G是子图H和K的不交并，那么P(G)=P(H)P(K).

引理1.3[5]如果图G是子图H和K的并，满足H∩K是一个顶点，那么

qP(G)=P(H)P(K).

1.3 广义剖分和三角剖分

定义1.6对于一个单纯复形K，找到其重心O，把重心O与单形的相应的顶点连接起来的一种剖分，称这种剖分为广义剖分.重复上述过程k次得到的图记为TkK(k≥1).

例单形K的一次广义剖分.

定义1.7拓扑空间X称为多面体，如果存在单纯复形K与同胚f:|K|≅X.这时把单纯复形K与同胚f组成的对偶(K,f)称为空间的一个三角剖分.

2 讨论图和剖分图的着色数目

对图剖分后区域着色问题进行研究，即计算图的广义剖分及三角剖分后的色多项式来进一步观察剖分后图的着色数目，看一看剖分前后图的着色数目是否有变化，通过前后图形的着色数目的对比进行一些题目的讨论并得到一些结论.为了便于计算把区域图G转化为其顶点的对偶图G*来研究.

(1)当n是奇数时，如果q≥3，则P(G*)≠0.

(2)当n是偶数时，如果q≥2，则P(G*)≠0.

图1 Gn与其对偶图Fig.1 Gn and its dual graph

注这说明n个区域图的着色情况为：当区域数为偶数时，可以用两种或两种以上的颜色着色就可以保证相邻区域着不同的颜色；而当区域数为奇数时，可以用3种或3种以上的颜色着色可以保证相邻区域着不同的颜色.

定理2.1设G(见图2)是由Gn和Gm构成，且Gn和Gm有一条公共边，则有

(1)当n与m中有一个为奇数，且q≥3时，P(G*)≠0.

(2)当n与m都为偶数，且q≥2时，P(G*)≠0.

图2 有一个公共边的平面图和其对偶图Fig.2 The plane graph with one common edge and its dual graph

证由引理1.2和引理1.3知道

当v=-1时,有

由引理2.1知：

n与m中有一个为奇数时，且当q≥3时，P(G*)≠0.

n与m都为偶数时，且当q≥2时，P(G*)≠0.

因此定理得证.

定理2.2设图G(见图2)是由Gn和Gm构成，且Gn和Gm有一条公共边，对G进行一次广义剖分后图T1G(见图3),则有：当q≥3时,P(T1G*)≠0.

图3 广义剖分的平面图Fig.3 Generalized division plane graph

证由引理1.2与引理1.3有

令v=-1时,有

注1定理说明有一个公共边的两个圆盘区域经一次广义剖分后可以用3种或3种以上的颜色着色能保证相邻区域着不同的颜色.给出了研究平面图着色的一种方法.

注2应用本文的方法可以讨论多面体及球面的三角剖分图的着色数目的性质.

[1] ALEXANDER J W.Topological invariants of knots and links[J].Trans Amer Math Soci,1928,30(2):275-306.

[2] JONES V F R.Hecke algebra representations of braid groups and link polynomials[J].Annals of Maths,1987,126:335-388.

[3] KAUFFMAN L H.New invariants in the theory of knots[J].The American Mathematical Monthly,1988,95(3):195-242.

[4] BOLLOBA B.Modern graph theory[M].Berlin:Springer,1998:335-378.

[5] TUTTE W T.Graph theory[M].Addison-Wesley, Reading, MA, 1969:253-284.

[6] BAXTER R J.q colorings of the triangular lattice[J].J Phys A:Math Gen,1986,19:2821-2839.

[7] ERNST C,SUMMERS D W.A calculus for rational tangles:applications to DNA recombination[J].Math Proc Camb Phil Soc,1990,108：489-515.

[8] ERNST C,SUMNERS D W.Solving tangles equations arising in a DNA recombination model[J].Math Proc Camb Phil Soc,1999,126:23-36.

[9] 韩友发，王英姣，沙欣，等.某些平面图着色的性质[J].吉林师范大学学报(自然科学版),2016，37(1)：36-40.

PolynomialofcoloringtheGraph

HANYoufa,KANGYunfeng,DONGTing

(School of Mathematics, Liaoning Normal University, Dalian 116029, China)

In this paper, we study properties of division plane graph with coloring by discussing the zeros of chromatic polynomial of graphs. We analyze the minimum number of ways to faces by coloring the graph, so that no two adjacent faces receive the same color, giving the important properties of the number of ways to color plane division figure. This paper gives a new study method of coloring plane division figure.We compute the dichromatic polynomial of graphs, summarize the coloring properties of decomposing plane before and after,and discuss the coloring properties of sphere division figure.We discuss the coloring number of the regional figureGnandGmwith a public side and their generalized division figure, and also discuss the coloring number of the triangulation figure of simple polyhedron and sphere.

plane graph;chromatic polynomial;generalized division;triangulation

O189.3

:A

2017-04-05

国家自然科学基金资助项目(11471151)

韩友发(1962- )，男，吉林长春人，辽宁师范大学教授，博士.

1000-1735(2017)03-0289-04

10.11679/lsxblk2017030289