广义Petersen图的点可约染色

Vertex Reducible Colorings of Generalized Petersen Graphs

摘要

图G的点可约染色是一个满足任意等度顶点的色集合相同的非正常边(全)染色.基于广义Petersen图G(n,k)的结构特征,应用组合分析法和构造函数法给出了图G(n,k)当阶数充分大时的点可约边(全)色数.

Abstract

A vertex reducible edge coloring of a graph G is an improper edge (total) coloring such that any two vertices with identical degree have the same color set. Based on the structural characters of the generalized Petersen graph G(n,k), we use combinatorial analysis method and constructive function method to give the vertex reducible edge (total) chromatic number of G(n,k) when its order is sufficiently large.

关键词

广义Petersen图 / 点可约边染色 / 点可约全染色

Key words

generalized Petersen graph / vertex reducible edge coloring / vertex reducible total coloring

参考文献

[1] 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.

[2] Zhang Z F, Liu L Z, Wang J F. Adjacent Strong Edge Coloring of Graphs[J]. Applied Mathematics Letters, 2002, 15(5): 623-626.

[3] Hatami H. Δ+300 Is a Bound on the Adjacent Vertex Distinguishing Edge Chromatic Number[J]. Journal of Combinatorial Theory (Series B), 2005, 95(2): 246-256.

[4] Balister P N, Györi E, Lehel J, et al. Adjacent Vertex Distinguishing Edge-Colorings[J]. SIAM Journal on Discrete Mathematics, 2007, 21(1): 237-250.

[5] Wang W F, Wang Y Q. Adjacent Vertex-Distinguishing Edge Colorings of K₄-Minor Free Graphs[J]. Applied Mathematics Letters, 2011, 24(12): 2034-2037.

[6] Hu J, Wang G H, Wu J L, et al. Adjacent Vertex Distinguishing Total Coloring of Planar Graphs with Maximum Degree 9[J]. Discrete Mathematics, 2019, 342(5): 1392-1402.

[7] 李敬文. 图的若干可区别染色[R]. 兰州: 西北师范大学, 2011.

[8] (Li J W. Several Distinguishable Colorings of Graphs[R]. Lanzhou: Northwest Normal University, 2011.)

[9] Dantas S, De Figueiredo C M H, Mazzuoccolo G, et al. On the Total Coloring of Generalized Petersen Graphs[J]. Discrete Mathematics, 2016, 339(5): 1471-1475.

[10] Zhu E Q, Li Z P, Shao Z H, et al. Acyclic 3-Coloring of Generalized Petersen Graphs[J]. Journal of Combinatorial Optimization, 2016, 31(2): 902-911.

[11] Chen M, Miao L Y, Zhou S. Strong Edge Coloring of Generalized Petersen Graphs[J]. Mathematics, 2020, 8(8): 1265-1-1265-10.

[12] Li Y Y, Chen L L. Injective Edge Coloring of Generalized Petersen Graphs[J]. AIMS Mathematics, 2021, 6(8): 7929-7943.

[13] Bondy J A, Murty U S R. Graph Theory with Applications[M]. London: Macmillan, 1976: 452-459.

[14] Brauer A, Shockley J E. On a Problem of Frobenius[J]. Journal für Die Reine und Angewandte Mathematik, 1962, 211: 215-220.

基金资助

国家自然科学基金(12261055)

甘肃省自然科学基金重点项目(24JRRA222)