递增型二色图K_(22)(3,7)及K_(27)(3,8)的生成 被引量：6

1

作者 黄文科 段禅伦 《内蒙古大学学报（自然科学版）》 CAS CSCD 1992年第2期157-162,共6页

n个顶点的完全图K_s,其边着色红或蓝,得K_n的二色图.当二色图既不包含蓝色团K_s,又不包含红色团K_y,则记作K_n(3,p).如果把K_n(3,p)成立的最大n值记为R(3,p),那未形如K_(n(3,p)(3,p)的一系列二色图与形为r(3,p)的一系列Ramsey数相关,已... n个顶点的完全图K_s,其边着色红或蓝,得K_n的二色图.当二色图既不包含蓝色团K_s,又不包含红色团K_y,则记作K_n(3,p).如果把K_n(3,p)成立的最大n值记为R(3,p),那未形如K_(n(3,p)(3,p)的一系列二色图与形为r(3,p)的一系列Ramsey数相关,已知R(3,p)=r(3,p)-1[1].本文讨论两个问题:(1)当p≤7时,给出二色图K_(R(3,p))(3,p)的递增性质,即K_(R(3,p))(3,p)可在K_(R(3,p-1))(3,p-1)上生成;(2)在二色图K_(22)(3,7)上生成K_(27)(3,8).从而知R(3,8)≥27,随知Ramsey数r(3,8)≥28. 展开更多

关键词 边色图 RAMSEY数 二色图 递增型

下载PDF 职称材料

关于Δ-临界图的构造

2

作者 皮晓明 李晓东 《纯粹数学与应用数学》 CSCD 2004年第4期368-371,共4页

研究了 Δ-临界图的构造 ,并且给出了一种由给定 Δ-临界图构造新的

关键词 边染色 边色数 △-临界图

下载PDF 职称材料

对Ramsey图(3,10)的初步探讨

3

作者 黄文科 段禅伦 《内蒙古大学学报（自然科学版）》 CAS CSCD 北大核心 2002年第6期707-713,共7页

用二色图的递阶生成方法,充分讨论了K39(3,10)的构造,并推想该图是(3,10)Ramsey图.

关键词 (3 p)Ramsey图 二色图 Kn(3 p)循环图 递阶生成方法 构造方法

下载PDF 职称材料

图的倍图与补倍图(英文) 被引量：21

4

作者 张忠辅 仇鹏翔 +3 位作者 张东翰 卞量 李敬文 张婷 《数学进展》 CSCD 北大核心 2008年第3期303-310,共8页

计算机科学数据库的关系中遇到了可归为倍图或补倍图的参数和哈密顿圈的问题.对简单图G,如果V(D(G))=V(G)∪V(G′),E(D(G))=E(G)∪E(G′)∪{v_iv_j′|v_i∈V(G),v_j′∈V(G′)且v_iv_j∈E(G)}那么,称D(G)是G的倍图,如果V((?)(G))=V(G)∪... 计算机科学数据库的关系中遇到了可归为倍图或补倍图的参数和哈密顿圈的问题.对简单图G,如果V(D(G))=V(G)∪V(G′),E(D(G))=E(G)∪E(G′)∪{v_iv_j′|v_i∈V(G),v_j′∈V(G′)且v_iv_j∈E(G)}那么,称D(G)是G的倍图,如果V((?)(G))=V(G)∪V(G′),E((?)(C))= E(G)∪E(G′)∪{v_iv_j′|v_i∈V(G),v_j′∈V(G′)and v_iv_j(?)E(G)},称(?)(C)是G的补倍图,这里G′是G的拷贝.本文研究了D(G)和(?)的色数,边色数,欧拉性,哈密顿性和提出了D(G)的边色数是D(G)的最大度等公开问题. 展开更多

关键词 倍图 补倍图 色数 边色数 欧拉图 哈密顿图

下载PDF 职称材料

联图P_m∨P_n的星边染色 被引量：9

5

作者 杨玉红 刘信生 陈祥恩 《西北师范大学学报（自然科学版）》 CAS 2008年第6期26-28,共3页

给出了联图Pn∨P2的星边色数和联图Pn∨Pn,Pm∨Pn星边色数的上界,同时也给出了一种简单易行的星边染色方法.

关键词 星边染色 星边色数 路与路的联图

下载PDF 职称材料

几类r-冠图的星边染色 被引量：1

6

作者 刘振轩 刘向阳 《湖北大学学报（自然科学版）》 CAS 2023年第3期384-389,共6页

图的星边染色是指图G的一个正常边染色使得G中没有长为4的路或圈是2-边染色的.图G的星边色数是指图G有星边染色的最小颜色数.本文中研究路、圈、扇、轮的r-冠图的星边染色问题.使用图分解法,反证法,染色构造法,组合分析法等方法和理论,... 图的星边染色是指图G的一个正常边染色使得G中没有长为4的路或圈是2-边染色的.图G的星边色数是指图G有星边染色的最小颜色数.本文中研究路、圈、扇、轮的r-冠图的星边染色问题.使用图分解法,反证法,染色构造法,组合分析法等方法和理论,得到4类r-冠图的星边色数. 展开更多

关键词 星边染色 星边色数 r-冠图 图分解法

下载PDF 职称材料

双外平面图的边染色 被引量：2

7

作者 孔立 倪亚洲 《山东教育学院学报》 2004年第6期88-89,93,共3页

双外平面图是一个平面图 ,它可以嵌入到平面上并使得它的顶点出现在两个面的边界上 ,本文证明对最大度至少为6的双外平面图是第一类的。

关键词 双外平面图 边色数 外平面图 边染色

下载PDF 职称材料

二边色图K_(35)(3,9)的生成 被引量：4

8

作者 段禅伦 黄文科 《内蒙古大学学报（自然科学版）》 CAS CSCD 1999年第6期770-773,共4页

ｎ 个顶点的完全图Ｋｎ ，用红色或蓝色对其边着色，得Ｋｎ 的二边色图．当Ｋｎ 的这种红蓝二边染色既不包含红色团Ｋ３ ，又不包含蓝色团Ｋｐ ，则将由Ｋｎ 经这种染色所得的图记为Ｋｎ （３，ｐ）．如果把Ｋｎ （３，ｐ）成立的最大ｎ... ｎ 个顶点的完全图Ｋｎ ，用红色或蓝色对其边着色，得Ｋｎ 的二边色图．当Ｋｎ 的这种红蓝二边染色既不包含红色团Ｋ３ ，又不包含蓝色团Ｋｐ ，则将由Ｋｎ 经这种染色所得的图记为Ｋｎ （３，ｐ）．如果把Ｋｎ （３，ｐ）成立的最大ｎ 值记为Ｒ（３，ｐ），那么形如ＫｉＲ（３，ｐ ） （３，ｐ）（ｉ＝ １，２，…，ｍ ，ｍ １）的一系列二边色图称为Ｒａｍ ｓｅｙ 极图，与形如ｒ（３，ｐ）的Ｒａｍ ｓｅｙ 数相关，即Ｒ（３，ｐ）＝ ｒ（３，ｐ）－ １．本文给出了Ｋ３５ （３，９）的一种构造，因而得到ｒ（３。 展开更多

关键词 完全图 边色图 RAMSEY数 二边色图

下载PDF 职称材料

广义图K(5,n)的边色数 被引量：3

9

作者 刘二根 《华东交通大学学报》 1997年第2期85-87,共3页

本文给出了完全图Ｋ５的广义图Ｋ（５，ｎ）的一种正常边着色法，从而解决了这类图的边色数．

关键词 正常边着色 边色数 广义图 完全图

下载PDF 职称材料

Remarks on Extremal Overfull Graphs

10

作者 Modjtaba Ghorbani 《Applied Mathematics》 2013年第8期1106-1108,共3页

An overfull graph is a graph whose number of its edges is greater than the product of its maximum degree and?[n/2] , where n is the number of vertices. In this paper, some extremals of overfull graphs are presented. W... An overfull graph is a graph whose number of its edges is greater than the product of its maximum degree and?[n/2] , where n is the number of vertices. In this paper, some extremals of overfull graphs are presented. We also classify all plannar overfull graphs. 展开更多

关键词 Overfull graph edge chromatic NUMBER Plannar graph

下载PDF 职称材料

完全图K_m与路P_n的笛卡尔积的强边色数 被引量：3

11

作者 王君帅 马登举 《牡丹江师范学院学报（自然科学版）》 2017年第2期27-30,共4页

图G的强边染色是指任意相邻与同一条边的两条边不能染相同的颜色的一种正常边染色.一个图G的强边色数χ'_s(G)是G的所有强边染色中所用颜色最少的强边染色使用颜色的数目.研究完全图K_m与路P_n的笛卡尔积K_m×P_n的强边染色问题... 图G的强边染色是指任意相邻与同一条边的两条边不能染相同的颜色的一种正常边染色.一个图G的强边色数χ'_s(G)是G的所有强边染色中所用颜色最少的强边染色使用颜色的数目.研究完全图K_m与路P_n的笛卡尔积K_m×P_n的强边染色问题,证明χ'_s( K_m×P_n)=1/2(m^2+3m),其中n≥2,m≥2. 展开更多

关键词 笛卡尔积 强边色数 完全图 路

下载PDF 职称材料

关于图的边着色的一个猜想 被引量：2

12

作者 林育青 《新疆大学学报（自然科学版）》 CAS 2020年第3期255-259,265,共6页

若G是简单图,v(G)是偶数,χ’(G)=△(G)+1,则存在点v∈V(G),使χ’(G-v)=χ’(G)=△(G)+1.本文对此进行了研究,当图G满足以下条件之一时:(1)设G是含有割边的连通图,χ’(G)=△(G)+1;(2)设G是连通图,κ’(G)=2,G中最多除两个2度顶点外,... 若G是简单图,v(G)是偶数,χ’(G)=△(G)+1,则存在点v∈V(G),使χ’(G-v)=χ’(G)=△(G)+1.本文对此进行了研究,当图G满足以下条件之一时:(1)设G是含有割边的连通图,χ’(G)=△(G)+1;(2)设G是连通图,κ’(G)=2,G中最多除两个2度顶点外,其它顶点的度数均为k(k>2),v(G)=2n+2,χ’(G)=△(G)+1;(3)设图G是k正则图,v(G)=2n+2,χ’(G)=△(G)+1;(4)设图G是有2n+2个顶点的连通图,且除点v的度小于k外,其它顶点的度都等于k,χ’(G)=△(G)+1;(5)设图G是有2n+2个顶点的连通图,且除点u,v,d(v)<d(u)<k外,其它顶点的度都等于k,χ’(G)=△(G)+1;此猜想也是成立的. 展开更多

关键词 边色数 正常的k边着色 正则图

下载PDF 职称材料

边临界图

13

作者 林育青 《南方职业教育学刊》 2011年第3期84-89,共6页

本文定义了边临界图,并对其进行了研究,主要得到了以下性质:1)若G是△(G)边临界图,则G必为星图S△(G);2)若G是△(G)+1边临界图,则G没有割边;3)若G是△(G)+1边临界图,则对任意边uv,有d(u)+d(v)≥△(G)+2;4)若G是△(G)=3的简单连通图,且ν... 本文定义了边临界图,并对其进行了研究,主要得到了以下性质:1)若G是△(G)边临界图,则G必为星图S△(G);2)若G是△(G)+1边临界图,则G没有割边;3)若G是△(G)+1边临界图,则对任意边uv,有d(u)+d(v)≥△(G)+2;4)若G是△(G)=3的简单连通图,且ν(G)是偶数,χ/(G)=△(G)+1,则存在点v∈V(G),使χ/(G-v)=χ/(G)=△(G)+1。此外,我们还提出猜想:"若G是简单图,G是△(G)+1边临界图,则ν(G)为奇数",并证明了此猜想与猜想"若G是简单图,ν(G)是偶数,χ/(G)=△(G)+1,则存在点v∈V(G),使χ/(G-v)=△(G)+1。"是等价的等结论。 展开更多

关键词 边临界图 边色数 正常的k边着色 完美图

下载PDF 职称材料

平面图为第一类图的一些充分条件(英文)

14

作者 邵振东 刘家壮 《高校应用数学学报（A辑）》 CSCD 北大核心 2004年第B12期577-581,共5页

给出了平面图为第一类图的边数的一些上界,并给出了平面图为第一类图的一些充分条件.

关键词 边色数 平面图

下载PDF 职称材料

图P_n^k的着色

15

作者 林育青 《安徽大学学报（自然科学版）》 CAS 北大核心 2008年第6期21-23,共3页

设k是一个正整数,在含有n个顶点的路Pn=v1v2…vn上,当且仅当两点的距离为k(k≥2)时增加一条边,这样所得到的图叫做Pnk(v1,vn),有时Pkn(v1,vn)也简记为Pnk.论文研究图Pnk的点着色、边着色和点、边全着色,得到图Pnk的点色数、边色数和图Pn... 设k是一个正整数,在含有n个顶点的路Pn=v1v2…vn上,当且仅当两点的距离为k(k≥2)时增加一条边,这样所得到的图叫做Pnk(v1,vn),有时Pkn(v1,vn)也简记为Pnk.论文研究图Pnk的点着色、边着色和点、边全着色,得到图Pnk的点色数、边色数和图Pnk满足点、边全着色猜想等结论. 展开更多

关键词 点色数 边色数 点、边全着色 图Pnk

下载PDF 职称材料

网格图的剖分图的强边染色

16

作者 黄会芸 《吉首大学学报（自然科学版）》 CAS 2012年第5期12-15,共4页

研究了3种网格图的剖分图的强边着色.网格图的剖分图是指用一个长为2的路去替换网格图的每条边.具体给出了六边形、四边形、三角形的网格剖分图的一种着色方法,以此为基础证明了Sχ′(Γs6)=4,Sχ′(Γs4)=5,Sχ′(Γs3)=7.

关键词 染色 强边染色 强边色数 网格图 剖分图

下载PDF 职称材料

1-外平面图的边面全色数(英文) 被引量：1

17

作者 王维凡 张克民 《应用数学》 CSCD 1999年第4期78-81,共4页

一个平面图Ｇ被称为１－外平面图如果存在一个顶点ｕ 使得Ｇ－ ｕ 是一个外平面图．本文证明了Ｍｅｌｎｉｋｏｖ 的边面染色猜想对所有１－外平面图成立．

关键词 边面全色数 1-外平面图 外平面图 平面图 染色

下载PDF 职称材料

哈林图的边面染色 被引量：1

18

作者 公全英 吴建良 《信息技术》 2008年第7期64-67,共4页

针对有限简单无向平图G,用V,E,F分别表示G的点集、边集和面集。如果边集E与面集F并的一个染色,使得任两相邻或相连元素得以分配不同的颜色,那么,称这种染色为平面G的边面染色。在图的边面染色中,使得两相邻元素染不同颜色所需的最小色数... 针对有限简单无向平图G,用V,E,F分别表示G的点集、边集和面集。如果边集E与面集F并的一个染色,使得任两相邻或相连元素得以分配不同的颜色,那么,称这种染色为平面G的边面染色。在图的边面染色中,使得两相邻元素染不同颜色所需的最小色数,称为平图的边面染色数。系统地证明:具有最大度至少为4的任何哈林图的边面染色数是可确定的;任何连通平图,其边面染色数为3的充分必要条件是阶至少为3的一条路或2连通3正则二分平图。 展开更多

关键词 边面染色数 哈林图 正则图

下载PDF 职称材料

关于简单图的边染色问题

19

作者 沈德安 刘焕平 《哈尔滨电工学院学报》 CSCD 1992年第1期77-83,共7页

本文给出了第一类图的几个充分条件,并对△-临界图建立了一些结果。

关键词 图论 第一类图 边染色问题 充分条件

下载PDF 职称材料

高度不正则图的两个结果

20

作者 张忠辅 王建方 王建中 《太原机械学院学报》 1990年第2期1-3,共3页

本文证明了阶不小于4的连通图和补图均为高度不正则图当且仅当图为4阶的路,同时证明了对于高度不正则图,其边色数等于最大度。

关键词 高度不正则图 自补图 边色数 图论

下载PDF 职称材料