概率方法讨论图的点可区别边色数的上界

详细信息    查看全文 | 推荐本文 |

英文篇名：Discussing the Upper Bounds on Vertex-Distinguishing Edge Coloring of a Graph by Probability Method 作者：崔俊峰 英文作者：CUI Junfeng;Department of mathematics,Longnan Teachers' College; 关键词：第一矩量原理 ; Lovász局部引理 ; 点可区别边染色 ; 上界 英文关键词：the principle of first moment;;the Lovász local lemma;;vertex distinguishing equitable edge coloring;;upper boundary 中文刊名：SDSX 英文刊名：Journal of Capital Normal University(Natural Science Edition) 机构：陇南师范高等专科学校数信学院; 出版日期：2019-02-15 出版单位：首都师范大学学报(自然科学版) 年：2019 期：v.40;No.174 基金：甘肃省高等学校科研项目(2015A-181) 语种：中文; 页：SDSX201901003 页数：3 CN：01 ISSN：11-3189/N 分类号：15-17

摘要

图的点可区别边染色是一个满足任意顶点色集合不相同的正常边染色,将所用的最少颜色数称为图的点可区别边色数.应用第一矩量原理和Lovász局部引理给出了图的点可区别边色数的两个上界.
        A vertex-distinguishing edge coloring of a graph is a proper edge coloring such that no two vertices have the same color sets,the minimum number of the required colors is called the vertex-distinguishing edge chromatic number. In this pape,we mainly obtain two upper bounds on vertex-distinguishing edge coloring of a graph by the Principle of first moment and the Lovász local lemma.

引文

[1] BONDY J A,MARTY U S R. Graph theory with applications[M]. New York:The Macmillan Press Ltd,1976.
    [2] BURRIS A C,SCHELP R H. Vertex-distinguishing proper edge-colorings[J]. Journal of Graph Theory,1997,26(2):73-82.
    [3]张东翰,张忠辅.图的邻点强可区别全色数的上界[J].数学进展,2011,40(2):168-172.
    [4]田京京.图的D(β)-点可区别边染色及其概率方法[D].兰州:西北师范大学,2007.
    [5]陆尚辉.概率方法与邻点可区别全染色的色数上界[D].北京:中央民族大学,2013.
    [6] MICHAEL M,BRUCE R. Graph Colouring and the Probabilistic Method[M]. New York:Springer,2002.