 北京大学期刊网　|　作者　　审稿人　　编委专家　　工作人员 首页　  |  　关于　  |  　浏览　  |  　投稿指南　  |  　新闻公告
 数学进展
 研究论文
 边覆盖临界图的一些性质 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
  卜月华,王丽霞. 稀疏平面图的2-距离染色[J]. 数学进展, 2019, 48(2): 145-155.  余梦蕾, 陈敏. 哈林图的弱边面染色[J]. 数学进展, 2018, 47(4): 509-516.  卜月华, 叶飘飘. 围长至少为 $\mathbf{5}$ 的平面图的 $\mathrm{\mathbf{injective}}$-染色[J]. 数学进展, 2018, 47(3): 363-372.  潘文华, 徐常青. 无$K_4$-图子式的图的邻和可区别边染色[J]. 数学进展, 2017, 46(6): 839-847.  卜月华, 商春慧. 不含4-圈平面图的2-距离染色[J]. 数学进展, 2017, 46(3): 342-354.  卜月华,严晓燕. 不含3, 4, 8-圈的平面图的2-距离染色[J]. 数学进展, 2015, 44(2): 208-218.  卜月华,严晓燕. 不含3, 4, 8-圈的平面图的2-距离染色[J]. 数学进展, 2014, 43(7): 13055-.  强会英,王洪申. \huge 图的邻点强可区别全色数的一个上界[J]. 数学进展, 2013, 42(6): 801-805.  张东翰，张忠辅. 图的邻点强可区别全色数的上界[J]. 数学进展, 2011, 40(2): 168-172.  王颜妮;孙磊;. 推广的Mycielski图和类推广的Mycielski图的(邻点可区别的)全染色[J]. 数学进展, 2010, 39(1): 88-94.  姚兵;张忠辅;姚明;李敬文;. 一类新的魔术染色(英文)[J]. 数学进展, 2008, 37(5): 571-583.  刁科凤,刘桂真. 混合超图的染色理论[J]. 数学进展, 2005, 34(2): 145-154.
Viewed
Full text

Abstract

Cited