您的位置：山东大学 -> 科技期刊社 -> 《山东大学学报（理学版）》

《山东大学学报(理学版)》 ›› 2024, Vol. 59 ›› Issue (2): 71-79.doi: 10.6040/j.issn.1671-9352.0.2022.413

•   • 上一篇    下一篇

广义Petersen图P（n, k）的等全着色

苏亚男(),仝春灵*(),李勇,苏森原   

  1. 山东交通学院信息科学与电气工程学院, 山东 济南 250357
  • 收稿日期:2022-07-28 出版日期:2024-02-20 发布日期:2024-02-20
  • 通讯作者: 仝春灵 E-mail:1846925207@qq.com;tongcl@sdjtu.edu.cn
  • 作者简介:苏亚男(1998—), 女, 硕士研究生, 研究方向为图论与组合优化. E-mail: 1846925207@qq.com
  • 基金资助:
    山东省自然科学基金重点项目(ZR2020KF010)

Equitable total coloring of generalized Petersen graphs P(n, k)

Yanan SU(),Chunling TONG*(),Yong LI,Senyuan SU   

  1. College of lnformation Science and Electrical Engineering, Shandong Jiaotong University, Jinan 250357, Shandong, China
  • Received:2022-07-28 Online:2024-02-20 Published:2024-02-20
  • Contact: Chunling TONG E-mail:1846925207@qq.com;tongcl@sdjtu.edu.cn

RichHTML

1

PDF (PC)

278

摘要：

广义Petersen图P(n, k)是着色问题中研究得最广泛的一类图, 但是当k(mod 4)=0时P(n, k)的全着色还有待进一步研究。采用计算机搜索和数学证明相结合的方法, 求得k(mod 16)=4, 8, 12以及k(mod 16)=0∧n(mod 2k)=0, 1, 2, 4时P(n, k)的等全色数。

关键词: 广义Petersen图, 等全着色, 等全色数

Abstract:

Generalized Petersen graphs P(n, k) are the most widely studied in coloring problems. However, the total chromatic number of P(n, k) for k(mod 4)=0 needs to be further studied. By combining computer searching and mathematics techniques, the equitable total chromatic number of P(n, k) for k(mod 16)=4, 8, 12 and k(mod 16)=0∧n(mod 2k)=0, 1, 2, 4 are obtained.

Key words: generalized Petersen graph, equitable total coloring, equitable total chromatic number

中图分类号: 

  • O157.5

图1

Petersen图P(5, 2)"

图2

导出子图Gi"

图3

n=9, 10, 11, 12时σ(P(n, 4))"

图4

n=17, 18, 19, 20时σ(P(n, 8))"

图5

n=33, 34时σ(P(n, 16))"

1 朱恩强. 图的全着色研究综述[J]. 广州大学学报(自然科学版), 2019, 18 (4):9-27.
ZHU Enqiang. A survey on total coloring of graphs[J]. Journal of Guangzhou University(Natural Science Edition), 2019, 18 (4):9-27.
2 BEHZAD M. Graphs and their chromatic numbers[D]. East Lansing: Michigan State University, 1965.
3 FU Hunglin. Some results on equalized total coloring[J]. Congressus Numerantium, 1994, 10, 111-119.
4 SÁNCHEZ-ARROYO A. Determining the total colouring number is NP-hard[J]. Discrete Mathematics, 1989, 78 (3):315-319.
doi: 10.1016/0012-365X(89)90187-8
5 MCDIARMID C J H, SÁNCHEZ-ARROYO A. Total colouring regular bipartite graphs is NP-hard[J]. Discrete Mathematics, 1994, 124, 155-162.
doi: 10.1016/0012-365X(92)00058-Y
6 WANG Weifan. Equitable total coloring of graphs with maximum degree 3[J]. Graphs and Combinatorics, 2002, 18 (3):677-685.
doi: 10.1007/s003730200051
7 DA SILVA A G, DANTAS S, SASAKI D. Equitable total coloring of complete r-partite p-balanced graphs[J]. Discrete Applied Mathematics, 2019, 261, 123-135.
doi: 10.1016/j.dam.2018.03.009
8 DA SILVA A G, DANTAS S, SASAKI D. Determining equitable total chromatic number for infinite classes of complete r-partite graphs[J]. Discrete Applied Mathematics, 2021, 296, 56-67.
doi: 10.1016/j.dam.2020.04.012
9 DA SILVA A G, DANTAS S, SASAKI D. Equitable total chromaic number of Kr×p for p even[J]. Electronic Notes in Theoretical Computer Science, 2019, 346, 685-697.
doi: 10.1016/j.entcs.2019.08.060
10 GUI Hao, WANG Weifan, WANG Yiqiao, et al. Equitable total-coloring of subcubic graphs[J]. Discrete Applied Mathematics, 2015, 184
11 FURMAŹCZYK H, ZUAZUA R. Equitable total coloring of corona of cubic graphs[J]. Discussiones Mathematicae Graph Theory, 2021, 41 (4):1147-1163.
doi: 10.7151/dmgt.2245
12 杨腾飞, 徐常青 . 3-退化图的全染色[J]. 山东大学学报(理学版), 2022, 57 (6):61-63.
doi: 10.6040/j.issn.1671-9352.0.2020.556
YANG Tengfei, XU Changqing. Total colorings of 3-degenerate graphs[J]. Journal of Shandong University(Natural Science), 2022, 57 (6):61-63.
doi: 10.6040/j.issn.1671-9352.0.2020.556
13 TONG Chunling, LIN Xiaohui, YANG Yuansheng, et al. Equitable total coloring of Cm□Cn[J]. Discrete Applied Mathematics, 2009, 157, 596-601.
doi: 10.1016/j.dam.2008.08.030
14 TONG Chunling, DONG Aijun, WANG Shouqiang, et al. Equitable total coloring of Kondel graph WΔ, n[J]. Journal of Computational Information Systems, 2014, 10 (22):9821-9829.
15 GONCALVES I F A, DANTAS S, SASAKI D. On equitable total coloring of snarks[J]. Procedia Computer Science, 2021, 195, 334-342.
doi: 10.1016/j.procs.2021.11.041
16 王晓丽, 王慧娟, 刘彬 . 最大度为7的平面图全染色[J]. 山东大学学报(理学版), 2017, 52 (8):100-106.
doi: 10.6040/j.issn.1671-9352.0.2016.363
WANG Xiaoli, WANG Huijuan, LIU Bin. Total coloring of planar graphs with maximum degree seven[J]. Journal of Shandong University (Natural Science), 2017, 52 (8):100-106.
doi: 10.6040/j.issn.1671-9352.0.2016.363
17 谭香. 一类最大度为6的平面图的全染色[J]. 山东大学学报(理学版), 2021, 56 (11):71-75.
doi: 10.6040/j.issn.1671-9352.0.2020.358
TAN Xiang. Total colorings of one type of planar graphs with maximum degree 6[J]. Journal of Shandong University (Natural Science), 2021, 56 (11):71-75.
doi: 10.6040/j.issn.1671-9352.0.2020.358
18 ZHANG Zhongfu, WANG Weifan, SHENG B, et al. On the equitable total colorings of some join graphs[J]. Journal of Information & Computational Science, 2005, 2 (4):829-834.
19 GONG Kun, ZHANG Zhongfu, WANG Jianfang. Equitable total coloring of Fn∨Wn[J]. Acta Mathematicae Applicatae Sinica, English Series, 2009, 25, 83-86.
doi: 10.1007/s10255-006-6031-4
20 VIVIK J V, GIRIJA G. An algorithmic approach to equitable total chromatic number of graphs[J]. Proyecciones Journal of Mathematics, 2017, 36 (2):307-324.
doi: 10.4067/S0716-09172017000200307
21 PRAVEENA K, VENKATACHALAM M. On equitable chromatic number of Tadpole graph Tm, n[J]. Communications Faculty of Sciences University of Ankara: Series A1 Mathematics and Statistics, 2019, 68 (2):1638-1646.
doi: 10.31801/cfsuasmas.546904
22 JAYARAMAN G, MUTHURAMAKRISHNAN D, MANIKANDAN K. Equitable total chromatic number of splitting graph[J]. Proyecciones (Antofagasta), 2019, 38 (4):699-705.
doi: 10.22199/issn.0717-6279-2019-04-0045
23 DANTAS S, DE FIGUEIREDO C, MAZZUOCCOLO G, et al. On the total coloring of generalized Petersen graphs[J]. Discrete Mathematics, 2016, 339 (5):1471-1475.
doi: 10.1016/j.disc.2015.12.010
24 TONG Chunling, LIN Xiaohui, YANG Yuansheng. Equitable total coloring of generalized petersen graphs P(n, k)[J]. Ars Combinatoria, 2019, 143, 321-336.
25 WATKINS M E. A theorem on Tait colorings with an application to the generalized Petersen graphs[J]. Journal of Combinatorial Theory, 1969, 6 (2):152-164.
doi: 10.1016/S0021-9800(69)80116-X
[1] 田双亮 . 若干广义Petersen图的邻点可区别全染色[J]. J4, 2008, 43(9): 42-44 .
[2] 刘大琨 王淑栋. 若干广义Petersen图的关联色数[J]. J4, 2008, 43(12): 48-51.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] 杨莹,江龙*,索新丽. 容度空间上保费泛函的Choquet积分表示及相关性质[J]. J4, 2013, 48(1): 78 -82 .
[2] 谢云龙,杜英玲 . 函数S-粗集与规律积分度量[J]. J4, 2007, 42(10): 118 -122 .
[3] 许春华,高宝玉*,卢磊,徐世平,曹百川,岳钦艳,张建 . 城市纳污河道废水化学强化一级处理的研究[J]. J4, 2006, 41(2): 116 -120 .
[4] 陈宏宇1, 张丽2. 不含弦5-圈和弦6-圈的平面图的线性2荫度[J]. 山东大学学报（理学版）, 2014, 49(06): 26 -30 .
[5] 梁霄, 王林山 . 一类S分布时滞递归神经网络的全局吸引子[J]. J4, 2009, 44(4): 57 -60 .
[6] 董新梅 . 关于Suryanarayana的若干问题[J]. J4, 2007, 42(2): 83 -86 .
[7] 宋玉丹,王士同*. 基于特征缺省的最小类内方差支持向量机[J]. J4, 2010, 45(7): 102 -107 .
[8] 史艳华1,石东洋2*. 伪双曲方程类Wilson非协调元逼近[J]. J4, 2013, 48(4): 77 -84 .
[9] 刘汝军,曹玉霞,周 平 . 利用小反馈实现离散非线性混沌系统的反控制[J]. J4, 2007, 42(7): 30 -32 .
[10] 王 怡,刘爱莲 . 时标下的蛛网模型[J]. J4, 2007, 42(7): 41 -44 .
版权所有 © 2018 《山东大学学报(理学版)》编辑部　
地址: 山东省济南市山大南路27号山东大学中心校区（250100）　电话: +86-0531-88366917　E-mail: xblxb@sdu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发