无三角形IC-可平面图的线性2-荫度

1

作者 闫清华 徐常青 《首都师范大学学报（自然科学版）》 2023年第5期1-5,共5页

设G为最大度为Δ的IC-可平面图。图G的线性2-荫度la_(2)(G)是将G分解为k个边不交森林的最小正整数k,其中森林的每个分支均为长至多为2的路。本文通过权转移方法研究了无三角形IC-可平面图的线性2-荫度,得到la_(2)(G)≤[△+1/2]+5。

关键词 IC-可平面图 线性2-荫度 权转移方法

下载PDF 职称材料

可平面图的DP-3-染色

2

作者 樊亚飞 张玉琴 《首都师范大学学报（自然科学版）》 2023年第1期1-10,共10页

Dvo?ák和Postle首次提出了DP-染色,该染色是列表染色的推广。本文证明了每个无{4,5,7,10}-圈的可平面图和每个无{4,5,8,10}-圈的可平面图都是DP-3-可染的,对这些可平面图的3-可选性进行了推广。

关键词 列表染色 DP-染色 可平面图 权转移规则

下载PDF 职称材料

可平面图的r-hued染色(英文)

3

作者 朱海洋 顾毓 +1 位作者 盛景军 吕新忠 《应用数学》 CSCD 北大核心 2016年第2期308-313,共6页

令k>0,r>0是两个整数.图G的一个r-hued染色是一个正常k-染色?使得每个度为d(v)的顶点v相邻至少min{d(v),r}个不同的颜色.图G的r-hued色数是使得G存在r-hued染色的最小整数k,记为χ_r(G).文章证明了,若G为不含i-圈,4≤i≤9,的可平... 令k>0,r>0是两个整数.图G的一个r-hued染色是一个正常k-染色?使得每个度为d(v)的顶点v相邻至少min{d(v),r}个不同的颜色.图G的r-hued色数是使得G存在r-hued染色的最小整数k,记为χ_r(G).文章证明了,若G为不含i-圈,4≤i≤9,的可平面图,则χ_r(G)≤r+5.这一结果意味着对于无4-9圈的可平面图,r-hued染色猜想成立. 展开更多

关键词 r-hued染色 可平面图 圈 Wagner猜想

下载PDF 职称材料

环面上外可平面图的最小圈基

4

作者 徐梅 任韩 党英 《华东师范大学学报（自然科学版）》 CAS CSCD 北大核心 2006年第5期72-75,共4页

研究环面上2-连通外可平面图G在嵌入Π的面宽fw(G)≥2时的圈基理论;给出在面宽fw(G)≥2和边宽ew(G)>m,m=max{li|1≤i≤f}时外可平面图G的最小圈基的结构,其中f记为Π的除Hamilton圈外的面迹数,l1,…,lf,为Π的对应面迹的长;并证明了... 研究环面上2-连通外可平面图G在嵌入Π的面宽fw(G)≥2时的圈基理论;给出在面宽fw(G)≥2和边宽ew(G)>m,m=max{li|1≤i≤f}时外可平面图G的最小圈基的结构,其中f记为Π的除Hamilton圈外的面迹数,l1,…,lf,为Π的对应面迹的长;并证明了G的最小圈基与其不同伦的两条长度之和最短的不可收缩圈之间存在一一对应． 展开更多

关键词 外可平面图 不可收缩圈 最小圈基

下载PDF 职称材料

外可平面图的圈基结构

5

作者 徐梅 任韩 党英 《内蒙古师范大学学报（自然科学汉文版）》 CAS 2005年第3期290-293,共4页

在ew(G)≥5的条件下,研究在平面和射影平面上2-连通的外可平面图的圈基结构,给出在这两种平面上嵌入的最小圈基.结果表明,平面上的最小圈基仅与面圈有关,射影平面上的最小圈基不仅与面圈有关,还与其不可收缩圈有着一一对应性.

关键词 外可平面图 不可收缩圈 最小圈基

下载PDF 职称材料

射影平面上外可平面图的最小圈基

6

作者 徐梅 党英 任韩 《淮阴师范学院学报（自然科学版）》 CAS 2005年第2期87-90,共4页

研究了射影平面上2 连通图的圈基结构,并给出了在嵌入的边宽度ew(G)≥5时外可平面图的最小圈基结构,证明了最小圈基与最短不可收缩圈之间的一一对应性.

关键词 外可平面图 不可收缩圈 最小圈基

下载PDF 职称材料

可平面图3可选择的一个充分条件

7

作者 陆华晶 王应前 《安庆师范学院学报（自然科学版）》 2011年第2期13-16,共4页

给G=(V,E)的每个顶点分配一个色列表L={L(v)|v∈V},若G有一个正常顶点染色φ,使得对每个顶点v∈V,都有φ(v)∈L(v),则称G是L可染的。若对G的每一个满足|L(v)|≥k,v∈V的L,G都是L可染的,则称G是k可选择的。本文通过权转移方法证明了每个... 给G=(V,E)的每个顶点分配一个色列表L={L(v)|v∈V},若G有一个正常顶点染色φ,使得对每个顶点v∈V,都有φ(v)∈L(v),则称G是L可染的。若对G的每一个满足|L(v)|≥k,v∈V的L,G都是L可染的,则称G是k可选择的。本文通过权转移方法证明了每个不含4,6,8,10圈的可平面图是3可选择的。 展开更多

关键词 选择性 可平面图 圈

下载PDF 职称材料

关于可平面图的3可选择性的一个注记 被引量：1

8

作者 郭宏斌 王应前 《安庆师范学院学报（自然科学版）》 2009年第3期4-7,共4页

给图G=(V,E)的每个顶点v∈V分配一个可用色集L(v),称L={L(v)|v∈V}为G的一张色列表,若对每个顶点v∈V,都可以从L(v)中找到一种颜色φ(v)染给v,使得φ(x)≠φ(y)对任意边xy∈E成立,则称G是L可染的。若对G的任意一张满足|L(v)|≥k对所有v... 给图G=(V,E)的每个顶点v∈V分配一个可用色集L(v),称L={L(v)|v∈V}为G的一张色列表,若对每个顶点v∈V,都可以从L(v)中找到一种颜色φ(v)染给v,使得φ(x)≠φ(y)对任意边xy∈E成立,则称G是L可染的。若对G的任意一张满足|L(v)|≥k对所有v∈V成立的色列表L,G都是L可染的,则称G是k可选择的。本文运用Discharging方法证明了每一个不含4,6,8圈且任意两个三角形的距离至少为2的可平面图是3可选择的。 展开更多

关键词 点染色 选择性 可平面图 圈 距离

下载PDF 职称材料

关于可平面图的3-列表染色的一个注记

9

作者 章齐君 王应前 《浙江师范大学学报（自然科学版）》 CAS 2009年第4期416-420,共5页

对于一个给定的平面图G,确定G是否为3-列表可染的是NP-困难的.运用D ischarging方法,证明了一个平面图是3-列表可染的充分条件,即不含相交i-圈与j-圈(4≤i≤j≤6),且三角形与5--圈的距离至少为3的平面图是3-列表可染的.所证结果改进了... 对于一个给定的平面图G,确定G是否为3-列表可染的是NP-困难的.运用D ischarging方法,证明了一个平面图是3-列表可染的充分条件,即不含相交i-圈与j-圈(4≤i≤j≤6),且三角形与5--圈的距离至少为3的平面图是3-列表可染的.所证结果改进了现有文献的相关结果. 展开更多

关键词 列表染色 可平面图 圈 距离

下载PDF 职称材料

最大外可平面图的树图 被引量：1

10

作者 李向东 《河北理工学院学报》 2000年第3期86-88,共3页

通过对最大外可平面图和 K临界图的研究给出三个主要结论( 1 )最大外可平面图的生成树有 2 p- 3* 3棵。( 2 )最大外可平面图的树图GT,Δ( GT)≥ p+ 1。( 3)临界图 G,当 K( G) =1时 ,树图 GT 是平凡图 ,当K( G) =2时 ;树图 GT是

关键词 树图 最大外可平面图 K临界图 生成树

下载PDF 职称材料

可平面图Hamilton回路存在的充要条件

11

作者 陈婵 《浙江师范大学学报（自然科学版）》 CAS 1990年第2期28-30,共3页

本文在可平面图具有Hamilton回路的必要条件:(?)(i—2)(fi—fi)=0的基础上,进一步探索了可平面图具有Hamilton回路存在的充要条件,得到了有关定理和推论。

关键词 可平面图 哈密顿回路 充要条件

下载PDF 职称材料

二部外可平面图中短路的最大个数

12

作者 杨柯 徐常青 兰永新 《南开大学学报（自然科学版）》 CAS CSCD 北大核心 2024年第4期1-10,共10页

记所有n阶二部外可平面图(包含Hamilton圈的二部外可平面图)中包含H的复制最多的图中H的复制的个数为f (A_(n),H)(f (H_(n),H)).记所有包含H的复制的个数为f (A_(n),H)(f (H_(n),H))的n阶二部外平面图(包含Hamilton圈的二部外可平面图)... 记所有n阶二部外可平面图(包含Hamilton圈的二部外可平面图)中包含H的复制最多的图中H的复制的个数为f (A_(n),H)(f (H_(n),H)).记所有包含H的复制的个数为f (A_(n),H)(f (H_(n),H))的n阶二部外平面图(包含Hamilton圈的二部外可平面图)的集合为F(A_(n),H)(F(H_(n),H)).确定了当n≥5时,f (A_(n),P_(2))的值及所有极图以及当n≥4时,f (H_(n),P_(3))的值及所有极图. 展开更多

关键词 二部外可平面图 HAMILTON圈 路

原文传递

无4-圈的IC-可平面图的线性2-荫度

13

作者 闫清华 向长媛 徐常青 《南开大学学报(自然科学版)》 CAS CSCD 北大核心 2023年第5期64-76,共13页

设G是最大度为Δ的IC-可平面图.图G的线性k-边染色是指G的一个映射φ:E(G)→{1,2,···,k}满足由染同一种颜色的边集导出的子图的连通分支均是长至多为2的路.图G的线性2-荫度是使G有一个线性k-边染色的最小正整数k.运用权... 设G是最大度为Δ的IC-可平面图.图G的线性k-边染色是指G的一个映射φ:E(G)→{1,2,···,k}满足由染同一种颜色的边集导出的子图的连通分支均是长至多为2的路.图G的线性2-荫度是使G有一个线性k-边染色的最小正整数k.运用权转移方法研究了IC-可平面图的线性2-荫度,得到无4-圈的IC-可平面图的线性2-荫度的上界为[△+1/2]+3. 展开更多

关键词 IC-可平面图 线性2-荫度 权转移方法

原文传递

不含相交三角形IC-可平面图的邻点可区别边染色

14

作者 李锦 徐常青 《山东大学学报（理学版）》 CAS CSCD 北大核心 2023年第12期134-139,共6页

设φ为图G的l-正常边染色,C_(φ)(u)为G中所有与顶点u关联的边所染颜色的集合。如果对G的任意边uv,都有C_(φ)(u)与C_(φ)(v)不同,则称染色φ为G的l-邻点可区别边染色,简记为l-avd染色。使图G有l-avd染色的最小正整数l称为图G的邻点可... 设φ为图G的l-正常边染色,C_(φ)(u)为G中所有与顶点u关联的边所染颜色的集合。如果对G的任意边uv,都有C_(φ)(u)与C_(φ)(v)不同,则称染色φ为G的l-邻点可区别边染色,简记为l-avd染色。使图G有l-avd染色的最小正整数l称为图G的邻点可区别边色数,记为χ_(a)′(G)。本文通过权转移方法研究不含相交三角形IC-正常可平面图G的邻点可区别边染色,得到χ_(a)′(G)≤max{Δ(G)+2,12}。 展开更多

关键词 邻点可区别边染色 权转移方法 IC-正常可平面图

原文传递

禁用C_(4)的IC-可平面图中C_(k)的最大个数

15

作者 王祎 兰永新 徐常青 《数学进展》 CSCD 北大核心 2023年第5期789-794,共6页

给定图G和H,如果图G不包含图H作为子图,则称图G是禁用H的.用ex_(ICP)(n,F,H)表示在所有禁用H且顶点数为n的IC-可平面图中,含与F同构的子图的最大个数.本文证明了对任意的k≥5,当n充分大时,有ex_(ICP)(n,C_(k),C_(4))=Θ(n^([k/3])).

关键词 广义Turán数 IC-可平面图 k-圈

原文传递

三类超越可平面图的结构及其约束数

16

作者 张华强 张欣 牛蓓 《应用数学学报》 CSCD 北大核心 2021年第6期838-846,共9页

如果一个图可以嵌入在平面内使得每条边最多被交叉一次,则称该图为1-可平面图.如果一个图可以嵌入在平面内使得任何两个交叉不共享关联点,则称该图为IC-可平面图.如果一个图可以嵌入在平面内使得任何两个交叉最多共享一个关联点,则称该... 如果一个图可以嵌入在平面内使得每条边最多被交叉一次,则称该图为1-可平面图.如果一个图可以嵌入在平面内使得任何两个交叉不共享关联点,则称该图为IC-可平面图.如果一个图可以嵌入在平面内使得任何两个交叉最多共享一个关联点,则称该图为NIC-可平面图.1-可平面图,IC-可平面图与NIC-可平面图是三类重要的超越可平面图,它们在模块网络,社交网络和生物网络上有着重要的应用.图的约束数是为了使图的支配数严格增加所需要删除的最少的边数,它是衡量网络脆弱性的一个重要参数.本文考虑1-可平面图,IC-可平面图与NIC-可平面图的结构,并利用得到的结构定理证明了它们的约束数分别最多是13,11与12. 展开更多

关键词 1-可平面图 IC-可平面图 NIC-可平面图 超越可平面图 约束数

原文传递

最大度至少为8的可平面图的全染色 被引量：4

17

作者 沈岚 王应前 《中国科学（A辑）》 CSCD 北大核心 2008年第12期1356-1364,共9页

证明了最大度至少为8且不含带弦5圈或带弦6圈的可平面图是9全可染的.

关键词 可平面图 全染色 最大度 圈 弦

原文传递

可平面图的线性2-荫度的新上限（英文） 被引量：1

18

作者 景昱波 王应前 《数学进展》 CSCD 北大核心 2016年第2期185-189,共5页

图G的线性2-荫度,记作la_2(G),是使得图G能够被剖分成k个边不交森林的最小正整数k,其中每个森林的每棵树是长度至多为2的路.本文给出了可平面图和没有三角形的可平面图的线性2-荫度的新上界,即证明了:(1)对于一般可平面图,当△≡0,3(mod... 图G的线性2-荫度,记作la_2(G),是使得图G能够被剖分成k个边不交森林的最小正整数k,其中每个森林的每棵树是长度至多为2的路.本文给出了可平面图和没有三角形的可平面图的线性2-荫度的新上界,即证明了:(1)对于一般可平面图,当△≡0,3(mod 4)时,la_2(G)≤[△/2]+9;当△≡1,2(mod 4)时,1a_2(G)≤[△/2]+8;(2)对于不含三角形的可平面图,当△≡0,3(mod 4)时,la_2(G)≤[△/2]+5;当△≡1,2(mod 4)时,la_2(G)≤[△/2]+6;其中△为图G的最大度. 展开更多

关键词 可平面图 不含三角形的可平面图 线性荫度 线性2-荫度

原文传递

平面图的距离2标号（英文）

19

作者 朱海洋 顾毓 吕新忠 《应用数学》 CSCD 北大核心 2016年第3期576-583,共8页

本文证明若G为?(G)≥6且不含4,5,6,7圈的平面图,则λ_(p,q)(G)≤(2q-1)?(G)+8p-4.这一结果暗含着对于?(G)≥6且不含4,5,6,7圈的平面图G,Wegner猜想成立.

关键词 L(p q)-标号 可平面图 圈 Wagner猜想

下载PDF 职称材料

两类平面图的指数集

20

作者 苗正科 《江苏师范大学学报（自然科学版）》 CAS 1994年第1期14-16,共3页

完全确定了极大可平面图与极大外可平面图的指数集。

关键词 本原有向图 本原无向图 极大可平面图 极大外可平面图 指数

下载PDF 职称材料