点色数相关论文
图G的点色数χ（G）是指图G存在正常k-顶点着色的k的最小值，图G的邻点可区别E-全色数χeat (G )是指图G存在邻点可区别E-全染色的k的最......
期刊
图论知识在电路的设计和计算机操作系统中预防出现死循环等一系列实际问题中的应用引发了对通过去掉图中的一些点(当然也去掉了与......
本报告包含了我在中国科学院数学与系统科学研究院系统所做博士后期间(2002.8-2004.8)所做的工作，其中主要有无三角形图的可选择性，......
一般说来,图的着色问题最早起源于著名的"四色问题",染色问题不但有着重要的理论价值,而且,它和很多实际问题有着密切联系,例如通......
在图的经典的顶点着色(或边着色)中，我们只要求任意两个相邻顶点(或相邻边)所着颜色不相同.如果还要求距离为二的顶点(或距离为二的......
设k是一个正整数,在含有 n个顶点的路Pn=v1v2…vn上,当且仅当两点的距离为 k(k≥2)时增加一条边,这样所得到的图叫做Pkn(v1,vn),有......
1970年,Gruenbaum 提出如下猜想“对于所有的整数 m>1和 n>2,均存在围长至少为 n 的 m 正则的 m 色图.”迄今为止,对于 n,m≥4,仅......
本文研究广义Petersen图GP(n,k)的点着色、边着色和点-边全着色,得到广义Petersen图GP(n,2)的点色数、边色数和全色数,同时还得到......
并研究了m＋1阶的星Sm和n＋1阶的扇Fn的联图Sm∨Fn的边染色和点染色，得到了Sm∨Fn的边色数和点色数．......
本文得到了有关乘积图的全色数的一些结果，并利用这些结果证明了Ｍｅｓｈ图和Ｔｏｕｒｓ－图均满足全色数猜想，特别，几乎所有的Ｍｅｓｈ－图都是第一类图。......
进一步研究发现，“图的色数问题研究”一文中的“算法”，实际上是构造图的着色方案的一种算法，也可能得到图的色数，也可能是一种近优值......
“四色猜想”提出至今将近１５０年，百年来它吸引了众多数学家们。１９７６年美国数学家Ａｐｐｅｌ和Ｈａｋｅｎ宣布：他们用电子计算机花了１２００多小时证明了“四色猜想”是成......
以极大平面图的结构研究为基础，采用常规的数学推理方法研究极大平面图的点色数问题。运用“并行（或平行）数学归纳法”证明了由“面内......
为了确定任意无向简单图Ｇ从分析点色数的出发，采用了作点集Ｖ的最小划分的方法，得到了一个点色数算法科给出了证明，从而解决了无向简单图......
以极大平面图的充分必要条件定理为基础，并考虑其性质定理：n（≥4）阶极大平面图Gn中每个结点的邻接点必构成圈。证明了极大平面图的3色......
以文献《极大平面图的色数研究》为基础，对“加点法”所遗漏的极大平面图进行再研究，证明了这些极大平面图也是四着色的。......
整数距离图是这样一类图G(Z，D)，其中V(G)=Z，两点u，υ之间有一条边相连，当且仅当｜u-υ｜∈=D，这里D∈N．本文确定了｜D｜≥4时某些距离图G(Z，D)的点......
分式色数和,点、色数是图的两个重要参数.本文在文献[1]的基础上给出了两类距离图G(Z,Dm,k,k+1)与G(Z,Dm,kk+1,K+2)的分式色数和点......
研究了图的连通控制数与全控制数、无赘数、点色数、点荫度等不变量之间的关系．将 文［２］中的一个结果ｒｃ（Ｇ）≤４ｉｒ（Ｇ）－２改进为ｒｃ（Ｇ）≤３ｉｒ（Ｇ）－２，且上界可达。......
Tutte关于3-连通图的结构定理表明：每一个3-连通图都可由某个轮图（也是Halin图）经顶点分裂逐步得到.这表明了Halin图在图结构研究中的......
一个给定的图是否存在用r种颜色的正常Pk着色？称该问题为图的（κ，r）路色数问题。本文研究其算法复杂性，并得到以下结果：对于任意给定的κ......
整数距离图以全体整数作为顶点集，顶点u、υ相邻当且仅当｜u-υ｜∈D，其中D是一个正整数集．对于m〉3，令Dm=[1,m]／[1,3]．本研究得到了G（Dm）的点......
设k是一个正整数,在含有n个顶点的路Pn=v1v2…vn上,当且仅当两点的距离为k（k≥2）时增加一条边,这样所得到的图叫做Pnk（v1,vn）,有时Pkn（v......
图染色问题是图论研究中的重要问题之一,本文针对双外平面图G的点色数进行研究,并证明了：（1）不加剖分点时,当顶点数为6n＋k（n=1,2,…）（k=1,......
若图G的任意两个相邻顶点染不同的颜色,则称为图G的一个正常染色.图G是k可着色的,若图G存在一个正常k着色.正常k着色的最小k值称为......
圆色数和分式色数是图的点色数的2个推广.当图的圆色数等于分式色数时,称此图是star extremal.本文研究了生成集为{±1,±......
1968年,Lovász提出了如下猜想:若G不是完全图,并且x(G)=m+n-1(其中m≥2,n≥2),则存在G的不相交子图G_1和G_2,使得x(G_1)=m和x......
通过极大平面图的结构研究，提出了构造极大平面图的三种方法，即“加点法”，“删点法”与“任意法”，建立了一个理论系统，包括１１个定义，１２个命......
本文解决了Halin图的点色数问题，并给出了一个可在线性时间内对Halin图进行点着色的算法．......
图G的点色数χ（G）是指图G存在正常k-顶点着色的k的最小值,图G的邻点可区别E-全色数χe at（G）是指图G存在邻点可区别E-全染色的k的最小......
为了推广图的点色数,引入图的两种广义点色数概念,即δ-色数和γ-色数.探讨了图与其补图的这两种色数关系,证实并推广了张忠辅等人......
确定了三角金字塔网TPL的点色数X（TPL）=4，当L≥4时，它的边色数为x＇（TPL）=12，它的全色数为疋；（TPL）=13．所得结果进一步完善了三角金字塔网TPL的......
