关于图的邻和可区别全染色的新方法

doi:10.6040/j.issn.1671-9352.0.2022.220

《山东大学学报(理学版)》 ›› 2023, Vol. 58 ›› Issue (6): 35-39.doi: 10.6040/j.issn.1671-9352.0.2022.220

关于图的邻和可区别全染色的新方法

常景智¹(),杨超^1,*(),姚兵²

1. 上海工程技术大学数理与统计学院，上海 201620
2. 西北师范大学数学与统计学院，甘肃兰州 730070

收稿日期:2022-04-18 出版日期:2023-06-20 发布日期:2023-05-23
通讯作者: 杨超 E-mail:changjingzhi1@163.com;yangchao@sues.edu.cn
作者简介:常景智(1996—)，男，硕士研究生，研究方向为图论及其应用. E-mail: changjingzhi1@163.com
基金资助:
国家自然科学基金资助项目(62072296)

A new method of neighbor sum distinguishing total coloring of graphs

Jingzhi CHANG¹(),Chao YANG^1,*(),Bing YAO²

1. School of Mathematics, Physics and Statistics, Shanghai University ofEngineering Science, Shanghai 201620, China
2. College of Mathematics and Statistics, Northwest Normal University, Lanzhou 730070, Gansu, China

Received:2022-04-18 Online:2023-06-20 Published:2023-05-23
Contact: Chao YANG E-mail:changjingzhi1@163.com;yangchao@sues.edu.cn

摘要/Abstract

摘要：

给出树的邻和可区别2-全染色方案，并结合三正则图最小消圈集的独立性以及消圈子图的无圈性，较为简洁地证明三正则图的邻和可区别全色数满足1-2猜想。进一步利用独立消圈集法确定r-正则图、Halin图以及路与路的笛卡尔乘积图的邻和可区别全色数。

关键词: 非正常全染色, 消圈集, 邻和可区别全染色, 1-2猜想

Abstract:

The neighbor sum distinguishing 2-total coloring of a tree is presented along with the independence of the minimum decycling set of a 3-regular graph and the acyclicity of the corresponding decycling subgraphs. This method provides a simple way to prove that the neighbor sum distinguishing total chromatic number of a 3-regular graph satisfies the 1-2 Conjecture. The independent decycling set method is used to determine the neighbor sum distinguishing total chromatic number of an r-regular graph, Halin graph, and Cartesian product graph of paths.

Key words: non-proper total coloring, decycling set, neighbor sum distinguishing total coloring, 1-2 Conjecture

中图分类号:

O157.5

常景智,杨超,姚兵. 关于图的邻和可区别全染色的新方法[J]. 《山东大学学报(理学版)》, 2023, 58(6): 35-39.

Jingzhi CHANG,Chao YANG,Bing YAO. A new method of neighbor sum distinguishing total coloring of graphs[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2023, 58(6): 35-39.

参考文献 9

1	KAROŃSKIM , ŁUCZAKT , THOMASONA .Edge weights and vertex colours[J].Journal of Combinatorial Theory: Series B,2004,91(1):151-157. doi: 10.1016/j.jctb.2003.12.001
2	KALKOWSKIM , KAROŃSKIM , PFENDERF .Vertex-coloring edge weightings: towards the 1-2-3-conjecture[J].Journal of Combinatorial Theory: Series B,2010,100(3):347-349. doi: 10.1016/j.jctb.2009.06.002
3	ADDARIO-BERRYL , DALALK , MCDIARMIDC ,et al.Vertex-colouring edge-weightings[J].Combinatorica,2007,27(1):1-12. doi: 10.1007/s00493-007-0041-6
4	ADDARIO-BERRYL , DALALK , REEDB A .Degree constrained subgraphs[J].Discrete Applied Mathematics,2008,156(7):1168-1174. doi: 10.1016/j.dam.2007.05.059
5	WANGT , YUQ L .On vertex-coloring 13-edge-weighting[J].Frontiers of Mathematics in China,2008,3(4):581-587. doi: 10.1007/s11464-008-0041-x
6	PRZYBYŁOJ .The 1-2-3 Conjecture almost holds for regular graphs[J].Journal of Combinatorial Theory: Series B,2021,147,183-200. doi: 10.1016/j.jctb.2020.03.005
7	PRZYBYŁOJ , WOŹNIAKM .On a 1, 2 Conjecture[J].Discrete Mathematics and Theoretical Computer Science,2010,12(1):101-108.
8	KALKOWSKI M. A note on the 1, 2-Conjecture[D]. Poznan: Adam Mickiewicz University, 2010.
9	RENH , YANGC , ZHAOT X .A new formula for the decycling number of regular graphs[J].Discrete Mathematics,2017,340(12):3020-3031. doi: 10.1016/j.disc.2017.07.011

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed

本文评价

推荐阅读 10

[1]	冒爱琴1, 2, 杨明君2, 3, 俞海云2, 张品1, 潘仁明1*. 五氟乙烷灭火剂高温热解机理研究[J]. J4, 2013, 48(1): 51 -55 .
[2]	李永明1, 丁立旺2. PA误差下半参数回归模型估计的r-阶矩相合[J]. J4, 2013, 48(1): 83 -88 .
[3]	董丽红1,2,郭双建1. Yetter-Drinfeld模范畴上的弱Hopf模基本定理[J]. J4, 2013, 48(2): 20 -22 .
[4]	廖明哲. 哥德巴赫的两个猜想[J]. J4, 2013, 48(2): 1 -14 .
[5]	赵同欣1,刘林德1*,张莉1,潘成臣2,贾兴军1. 紫藤传粉昆虫与花粉多型性研究[J]. 山东大学学报（理学版）, 2014, 49(03): 1 -5 .
[6]	王开荣,高佩婷. 建立在DY法上的两类混合共轭梯度法[J]. 山东大学学报（理学版）, 2016, 51(6): 16 -23 .
[7]	杨伦，徐正刚，王慧，陈其美，陈伟，胡艳霞，石元，祝洪磊，曾勇庆. RNA干扰沉默PID1基因在C2C12细胞中表达的研究[J]. J4, 2013, 48(1): 36 -42 .
[8]	刘婷婷,陈志勇,李晓琴*,杨文志. 随机变量序列的Berry-Esseen界[J]. 山东大学学报（理学版）, 2014, 49(03): 101 -106 .
[9]	刘艳萍,吴群英. 优化权重下高斯序列最大值几乎处处中心极限定理[J]. 山东大学学报（理学版）, 2014, 49(05): 50 -53 .
[10]	罗斯特,卢丽倩,崔若飞,周伟伟,李增勇*. Monte-Carlo仿真酒精特征波长光子在皮肤中的传输规律及光纤探头设计[J]. J4, 2013, 48(1): 46 -50 .

关于图的邻和可区别全染色的新方法

A new method of neighbor sum distinguishing total coloring of graphs

RichHTML

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献 9

相关文章 2

多维度评价

本文评价

推荐阅读 10

[1]	宋红杰,巩相男,潘文华,徐常青. Halin图的邻和可区别全染色[J]. 山东大学学报（理学版）, 2016, 51(4): 65-67.
[2]	姚京京, 徐常青. 最大度为3或4的图的邻和可区别全染色[J]. 山东大学学报（理学版）, 2015, 50(02): 9-13.