若干联图的L(2,1)-边染色算法  

L(2,1)-edge coloring algorithm for some composite graphs

作　　者：朱利娜 李敬文[1] 孙帅 ZHU Lina;LI Jingwen;SUN Shuai(School of Electronic and Information Engineering,Lanzhou Jiaotong University,Lanzhou 730070,China)

机构地区：[1]兰州交通大学电子与信息工程学院,甘肃兰州730070

出　　处：《中山大学学报（自然科学版）（中英文）》2023年第3期175-183,共9页Acta Scientiarum Naturalium Universitatis Sunyatseni

基　　金：国家自然科学基金(11961041,62062049,11461038);甘肃省科技计划(21ZD8RA008)。

摘　　要：图的距离染色问题是频率分配问题的一种图模型,所谓的频率分配问题是指某一区域的不同电台要使用无线电波发送信号,为了避免干扰,位置较近的电台需要使用不同的频道,当电台距离特别近时,它们之间需要间隔至少2个信道。L(2,1)-边染色是指距离为1的两条边的色数差值大于等于2,距离大于1的两条边的色数不同。本文针对随机图设计了一种L(2,1)-边染色算法,实验结果表明,该算法能够解决有限点内随机图的L(2,1)-边染色问题。通过分析实验结果,发现了3类单圈图的染色特性,定义C_(3)↑P_(n)↑S_(m),C_(n)↓S_(m)和C_(n)↑S_(m)分别来刻画这三类单圈图,并给出相关定理及其证明。The distance coloring problem of graph is a graph model for frequency allocation problem.The so-called frequency allocation problem refers to that different radio stations in a certain area need to use radio waves to send signals.In order to avoid interference,stations in close proximity need to use different channels,and when stations are particularly close,they need to be separated by at least two channels.L(2,1)-edge coloring means that the chromatic number difference of two edges with distance 1 is greater than or equal to 2,and the chromatic number of two edges with distance greater than 1 is different.In this paper,an L(2,1)-edge coloring algorithm is designed for random graphs.According to the experimental results,it is shown that the L(2,1)-edge coloring problem of random graphs in finite points can be solved through the algorithm.Meanwhile,the coloring properties of three kinds of unicyclic graphs are found here,and we define C_(3)↑P_(n)↑S_(m),C_(n)↓S_(m) and C_(n)↑S_(m) to characterize these three kinds of unicyclic graphs respectively.The related theorems and proofs are given as well.

关 键 词：L(2 1)-边染色 色数 单圈图 算法 

分 类 号：O157.5[理学—数学]