共查询到20条相似文献,搜索用时 0 毫秒
1.
2.
低度平面图的边面全色数 总被引:2,自引:0,他引:2
王维凡 《高校应用数学学报(A辑)》1993,(3):300-307
平面图G(V,E,F)的边面全色数X,(G)是使得集合E(G)∪ F(G)中相邻和相关联的元素均染为不同颜色的最少颜色数。本文提出猜想:对任何平面图G,有△(G)≤X,(G)≤△(G)+3;并对顶点度不超过3或面度均为3的平面图证明了这个猜想为真。 相似文献
3.
平面图 G(V,E,F)的点面全色数 xs(G)是使得集合 V(G)U F(G)中相邻和相关联的元素均染为不同颜色的最少颜色数.本文证明了:(1)若 G 为极大平面图,则4≤xs(G)≤6;且 xs(G)=4当且仅当 G 为点次模3-正则图.(2)若 G 为△(G)≤3的简单平面图,则 xs(G)≤6.一、引言本文限于考虑平面图 G(V,E,F),其中 V,E,F 分别为 G 的点集合,边集合和面集 相似文献
4.
简要介绍了图的关联着色问题的起源、发展情况及目前已有的结论,对一类特殊的图——极大外平面图(△≠6),给出了其关联色数. 相似文献
5.
6.
7.
8.
极大外平面图在边界条件下的4染色 总被引:6,自引:0,他引:6
本文利用极大外平面图的对象变换研究它的染色,并给出了特征向量的概念,证明了任意两上有公共界环的极大外平面图都可以通过一系列对角变换互相得到,进而证明了有公共标定界环的两个极大外平面图在某些条件下有公共4染色。 相似文献
9.
如果图G的一个正常边染色使得G中没有长为4的路或4-圈是2-边染色的,则称此染色是G的一个星边染色.对G进行星边染色所需的最少颜色数称为G的星边色数,记作x′s(G).该文证明了最大度为4的极大外平面图的星边色数等于6,对任一n(≥8)阶极大外平面图Gn,有6≤x′s(Gn)≤n-1成立,并且上界和下界都是可达的. 相似文献
10.
11.
12.
极大外平面图的邻强边色数 总被引:1,自引:0,他引:1
本文证明了对极大外平面图 G,Δ(G) χ′as(G)≤ Δ(G) +1,且 χ′as(G) =Δ(G) +1,当且仅当存在两个最大度点相邻 .其中Δ (G)、χ′as(G)分别表示图 G的最大度和邻强边色数 . 相似文献
13.
1988年,张忠输等证明了对于△(G)≥3的外平面图G,全色数XT(G)=△(G)+1.本文给出此结论一个简单证明,方法是全新的. 相似文献
14.
设G为Δ(G)≥5的外平面图且xef(G)为G的边面全色数。本文证明了:Δ(G)≤xef(G)≤Δ(G)+1,且xef(G)=Δ(G),当且仅当G含有一个由内边组成且覆盖G的每一个最大度点的匹配。 相似文献
15.
一个平面图G被称为1-外平面图如果存在一个顶点u 使得G- u 是一个外平面图.本文证明了Melnikov 的边面染色猜想对所有1-外平面图成立. 相似文献
16.
洪文豪邱正萍宋玲汤自凯 《数学理论与应用》2020,(3):77-84
设G是一个由n个顶点,m条边构成的简单连通图.如果图G所有顶点的度相同,则我们称图G是正则图,反之,称图G是不规则图.对于一个不规则图G,由其不变量定义的度偏差为s(G)=∑_(i=1)^(n)|d_(i)-2m/n|,其中d_(i)表示G的第i个顶点的度.本文给出极大外平面图的度偏差的极大值和极小值,并刻画其对应的极值图. 相似文献
17.
所谓图R_n是指具有如下结构的平面图:R_n=(V,E),其中顶点集合V={u_1,u_2,…,u_n}U{v_1,v_2,…,v_n},边集合E={u_iu_(i+1),v_iv_(i+1),u_iv_i,u_iv_(i+1)|i=1,2,…,n},其中u_(n+1)=u_1,v_(n+1)=v_1.通过研究R_n的邻点可区别关联着色,给出了当n=4,n是3或者5的正整数倍时,R_n的邻点可区别关联色数. 相似文献
18.
19.
设e是3连通图G的一边。如果G-e是某个3连通图的剖分,则称e是G的可去边。用v表示G的顶点数,本文证明了当v≥6时,3连通平面图G的可去边数的下界是v+4/2,此下界是可以达到的。 相似文献
20.
给定平面图G的一个正常κ-顶点染色φ:V(G)→{1,2,…,κ},若对G的每个面f,与f关联的顶点所染颜色的极大颜色在与f关联的顶点中仅出现一次,则称φ是图G的面唯一极大κ-染色.图G存在面唯一极大κ-染色的κ的最小值称为G的面唯一极大色数,记作χfum(G).本文研究了阿基米德图的面唯一极大色数,证得若图G是阿基米德图,则χfum(G)=4. 相似文献