不含相邻 5^--圈的平面图的均匀染色  

Equitable Coloring of Planar Graphs without Adjacent 5--Cycles

作　　者：吴弦禧 黄丹君[1] 

机构地区：[1]浙江师范大学,数学科学学院,浙江 金华

出　　处：《应用数学进展》2023年第3期1035-1044,共10页Advances in Applied Mathematics

摘　　要：图 G 的一个均匀 k-染色是指 G 的一个正常 k-点染色且满足任意两个色类的顶点数之差的绝对值至多为 1 。 若 G 存在一个均匀 k-染色,则称 G 是均匀 k-可染的。 本文将运用权转移方法证明:不含相邻 5−-圈的平面图是均匀 k-可染的,其中 k ≥▏max{∆(G), 5} 且 ∆(G) 是图 G 的最大度。An equitable k-coloring of a graph G is a proper vertex coloring such that the difference in the order of any two color classes is at most one. The graph G is said to be equitablyk-colorable if G has an equitable k-coloring. In this paper, we will prove that every planar graph without adjacent 5−-cycles is equitably k-colorable for k ≥ max{∆(G), 5}, where ∆(G) is the maximum degree of G.

关 键 词：均匀 k-染色 平面图 圈 

分 类 号：O15[理学—数学]