排序方式: 共有31条查询结果,搜索用时 0 毫秒
1.
如果一个连通图不包含长度大于或等于4的圈,那么这个图被称为花形图,在这篇文章中,我们证明了每一个花形图的对策染色数至多为5。 相似文献
2.
王维凡 《辽宁大学学报(自然科学版)》1992,19(1):16-21
本文证明了对每一个△(G)≥3的外平面图G,有X~c(G)≤△(G)+3,其中X~c(G)为G的完备色数,△(G)为G的顶点最大度。 相似文献
3.
王维凡 《辽宁大学学报(自然科学版)》1995,(3)
连通图的生成树是该图的极小连通生成子图.本文通过Cayley公式及求解递推关系方程,分别求出了三类简单外平面图A_m,B_m和Z_m的生成树的棵数,给出了它们的递推关系式及通项表达式. 相似文献
4.
两类积图的(2,1)-全标号 总被引:3,自引:0,他引:3
图G的一个k-(2,1)-全标号是一个映射f:V(G)∪E(G)→{0,1,…,k},使得任意2个相邻的点和相邻的边有不同值,且任一对相关联的点和边的值差的绝对值至少为2.G的(2,1)-全标号数λt2(G)定义为G有一个k-(2,1)-全标号的最小的k值.刻画了圈与圈、路与路笛卡尔积图的(2,1)-全标号数. 相似文献
5.
研究了2-外平面图的无圈边染色问题.运用删点变换,得到了2-外平面图的结构性质;继而,运用数学归纳法,得到了图的一个无圈(Δ(G)+3)-边染色,即得到:若G是一个2-外平面图,则a’(G)≤Δ(G)+3. 相似文献
6.
7.
王维凡 《辽宁大学学报(自然科学版)》1995,22(A00):21-25
平面图G(V,E,F)的完备色数χc(G)是使得集合V(G)∪E(G)∪F(G)中的相邻点,相邻边、相邻面、相关联的点边、相关联的点面及相关联的边面均染为不同颜色的最少颜色数。一个无割点的外平面称为开外平面图。如果它的每一个内面的边界至少含一条外边。本文证明了:若G为开外平面图且其顶点最大度△(G)≥6,则χc(C)=△(G)+1。 相似文献
8.
9.
王维凡 《辽宁大学学报(自然科学版)》1994,(4)
本文证明了:若G为简单外平面图,则(i)当Δ(G)≥4时,Δ(G)≤Xe(G)≤Δ(G)+1;(ii)当Δ(G)=3时,4≤Xe(G)≤5,且Xe(G)=5当且仅当G-E'含有奇圈分支,其中E'为G的割边集合,Δ(G)为G的点最大度,Xe(G)为G的边面全色数。 相似文献
10.
第一类平面图的一个充分条件 总被引:1,自引:0,他引:1
对于最大度为5的平面图,既有第一类,也有第二类.运用Discharge方法以及临界图的一些重要性质证明了:每个最大度为5且不含相交三角形的简单平面图的边色数等于5,即这样的平面图是第一类的.因此,给出了最大度为5的平面图分类的一个特征刻画. 相似文献