![](https://csdnimg.cn/release/download_crawler_static/18778670/bg1.jpg)
第 卷第 期 浙江师范大学学报自然科学版 Vol No
年 月 Journal of Zhejiang Normal UniversityNatSci Feb
文章编号
不 含 和 圈 的 平 面 图 的 均 匀 染 色
王维凡桂浩
浙江师范大学 数理与信息工程学院浙江 金华
摘要一个图 G 是均匀 k可染的如果 G 有一个 k染色V
V
V
k
使得对任何 i jk 有
V
i
V
j
应用细致的结构分析和经典的 discharging 方法证明了最大度 且没有 圈的平
面图是均匀 可染的
关键词均匀染色平面图圈最大度
中图分类号O文献标识码A
Equitable coloring of planar graphs without and cycles
WANG WeifanGUI Hao
College of Mathematics Physics and Information Engineering Zhejiang Normal University Jinhua Zhejiang China
Abstract A graph G was denoted equitably kcolorable if G admitted a proper vertex kcoloring such that the
sizes of any two color classes differed by at most It was showed that every planar graph G with and
without and cycles was equitably kcolorable for any kThe present proof was based on structural
analysis and discharging technique
Key words equitably coloring planar graph cycle maximum degree
引言
本文所指的图均为有限的无向的简单图给定一个图 G分别用 VGEG G GG
简记为 表示 G 的顶点集合边集合阶最小度和最大度一个图 G 的顶点 k染色是指 VG到颜色
集合k的一个映射 使得任意 个相邻的顶点 x 和 y 满足 xyG 的色数 G定义
为使得 G 有 k染色的最小整数 k给定 G 的一个 k染色 用 V
i
表示染颜色 i 的顶点集合如果对任一
对 i jk有 V
i
V
j
那么就称 为 G 的均匀染色或者 G 是均匀 k可染的图 G 的
均匀色数定义为
e
G mink G 是均匀 k可染的
显然
e
GG且不等式可以严格成立 年Meyer
引进了图的均匀染色的概念并提
出以下猜想
猜想 1若 G 不是完全图也不是奇圈则
e
G
收文日期修订日期
基金项目国家自然科学基金资助项目
作者简介王维凡 男辽宁沈阳人教授博士生导师研究方向图论与组合优化