Please wait a minute...
北京大学期刊网 | 作者  审稿人  编委专家  工作人员

首页   |   关于   |   浏览   |   投稿指南   |   新闻公告
数学进展
研究论文
边覆盖临界图的一些性质
Some Properties of Edge Covered Critical Graphs

宋慧敏,刘桂真
SONG Hui-min, LIU Gui-zhen

山东大学威海分校数学系,山东大学数学与系统科学学院 威海,山东, 264209 山东大学数学与系统科学学院,济南,山东, 250100,济南,山东, 250100
(1. Dept. of Math., Shandong Univ. at Weihai, Weihai, Shandong, 264209, P. R. China; 2. School of Math, and System Science, Shandong Univ., Jinan, Shandong, 250100, P. R. China

收稿日期: 2004-02-25
出版日期: 2004-02-25

96
浏览

引用导出
0
    /   /   推荐

摘要 设G是一个简单图,其顶点集为V(c)而边集为E(G),S(?)E(G)称为G的一个覆盖,如果由S导出的子图为G的一个生成子图. G的边覆盖色数xc'(G)是E(G)所能划分成的最大边覆盖数.已知δ-1≤xc'(G)≤δ,由此将xc'(G):δ的图称为CI类图,否则称为CII类图.若G是连通CII类图,且G不是完全图,对任意的u,v∈V(G),e=uv(?)E(G),都有xc'(G+e)>xc'(G)成立,则称G为边覆盖临界的.本文研究了边覆盖临界图的一些性质.即若G为边覆盖临界图,则对任意的u,v∈V(G),若e=uv(?)E(G),总存在W∈{u,v},有d(w)≤2δ-2,且ω至少与max{d(w)-δ+1,3d(ω)-4δ+4}个最小度顶点相邻.
关键词 边覆盖染色边覆盖临界图最小度顶点染色    
Abstract:Let G be a graph with vertex set V(G) and edge set E(G). A subset of E(G) is called an edge covering of G if the subgraph induced by S is a spanning subgraph of G. The maximum number of edge coverings which construct a partition of E(G) is called the edge covered chromatic index of G and denoted by x'c(G). It is well known that δ - 1 ≤ x'c(G) ≤ δ. If x'c(G) = δ, then G is called a graph of CI class, otherwise G is called a graph of CII class. Let G be a connected and not complete graph of CII class. If for any u, v ∈ V(G) and e = uv (?) E(G), we have x'c(G + e) > x'c(G), then G is called an edge covered critical graph. In this paper some properties of edge covered critical graphs are discussed. It is proved that if G is an edge covered critical graph, then for any u, v ∈ V(G) and uv (?) E(G) there is a vertex w ∈{u, v} such that d(w) ≤ 26 - 2 and w is adjacent to at least max{d(w) - δ + 1, 3d(w) - 4δ + 4} vertices with minimum degree in G.
Key words edge covered critical graph    vertex with minimum degree    coloring
[1] 卜月华,王丽霞. 稀疏平面图的2-距离染色[J]. 数学进展, 2019, 48(2): 145-155.
[2] 余梦蕾, 陈敏. 哈林图的弱边面染色[J]. 数学进展, 2018, 47(4): 509-516.
[3] 卜月华, 叶飘飘. 围长至少为 $\mathbf{5}$ 的平面图的 $\mathrm{\mathbf{injective}}$-染色[J]. 数学进展, 2018, 47(3): 363-372.
[4] 潘文华, 徐常青. 无$K_4$-图子式的图的邻和可区别边染色[J]. 数学进展, 2017, 46(6): 839-847.
[5] 卜月华, 商春慧. 不含4-圈平面图的2-距离染色[J]. 数学进展, 2017, 46(3): 342-354.
[6] 卜月华,严晓燕. 不含3, 4, 8-圈的平面图的2-距离染色[J]. 数学进展, 2015, 44(2): 208-218.
[7] 卜月华,严晓燕. 不含3, 4, 8-圈的平面图的2-距离染色[J]. 数学进展, 2014, 43(7): 13055-.
[8] 强会英,王洪申. \huge 图的邻点强可区别全色数的一个上界[J]. 数学进展, 2013, 42(6): 801-805.
[9] 张东翰,张忠辅. 图的邻点强可区别全色数的上界[J]. 数学进展, 2011, 40(2): 168-172.
[10] 王颜妮;孙磊;. 推广的Mycielski图和类推广的Mycielski图的(邻点可区别的)全染色[J]. 数学进展, 2010, 39(1): 88-94.
[11] 姚兵;张忠辅;姚明;李敬文;. 一类新的魔术染色(英文)[J]. 数学进展, 2008, 37(5): 571-583.
[12] 刁科凤,刘桂真. 混合超图的染色理论[J]. 数学进展, 2005, 34(2): 145-154.
Viewed
Full text


Abstract

Cited

首页 · 关于 · 关于OA · 法律公告 · 收录须知 · 联系我们 · 注册 · 登录


© 2015-2017 北京大学图书馆 .