树图的点可约全染色  

Vertex Reducible Total Coloring of Trees

作　　者：李敬文[1] 王丽 Li Jingwen;Wang Li(School of Electronic and Information Engineering,Lanzhou Jiaotong University,Lanzhou 730070,China)

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

出　　处：《南开大学学报（自然科学版）》2024年第5期102-110,共9页Journal of Nankai University(Natural Sience)

基　　金：国家自然科学基金(11961041,62262038);甘肃省媒体融合技术与传播重点实验室(21ZD8RA008)。

摘　　要：针对树形网络拓扑结构在特殊情景下的染色问题,借鉴传统的遗传算法、模拟退火算法等智能算法思路,设计了一种新的点可约全染色算法,能够寻找有限点内随机图的点可约全色数.通过分析实验结果,根据染色规律总结出了几类树图的相关定理,并给出猜想:树图的点可约全色数至多为最大度的两倍.Aiming at the coloring problem of tree network topology under special scenarios,a new vertex reducible total coloring algorithm is designed by drawing on the ideas of intelligent algorithms such as traditional genetic algorithm and simulated annealing algorithm,which can find the vertex reducible total chromatic number of random graphs within a finite number of points.By analyzing the experimental results,the relevant theorems of several types of tree graphs are summarized according to the coloring rules,and a conjecture is given:the vertex reducible total chromatic number of a tree graph is at most twice the maximum degree.

关 键 词：点可约全染色 点可约全色数 染色算法 树图 

分 类 号：TP301.5[自动化与计算机技术—计算机系统结构]