极大平面图的结构与着色理论(4)σ-运算与Kempe等价类

• 作者: 许进
• 来源期刊: 电子与信息学报
• 学科: 数学
• 关键词: Kempe极大平面图 Kempe变换 σ-运算 Kempe等价类 σ-特征图 2-色耳
• 年，卷（期）: 2016,（7）
• 所属期刊栏目: 论文
• 页码范围: 1557-1585
• 页数: 29页
• 分类号: O157.5
• 字数: 11943字
• 语种: 中文
• DOI: 10.11999/JEIT160483

摘要

设G是一个k-色图,若G的所有k-着色是Kempe等价的,则称G为Kempe图.表征色数≥3的Kempe图特征是一尚待解决难题.该文对极大平面图的Kempe等价性进行了研究,其主要贡献是:(1)发现导致两个4-着色是Kempe等价的关键子图为2-色耳,故对2-色耳的特征进行了深入研究;(2)引入σ-特征图,清晰地刻画了一个图中所有4-着色之间的关联关系,并深入研究了σ-特征图的性质;(3)揭示了垂色非Kempe极大平面图的Kempe等价类可分为树型,圈型和循环圈型,并指出这3种类型可同时存在于一个极大平面图的4-着色集中;(4)研究了Kempe极大平面图特征,给出了该类图的多米诺递推构造法,以及两个Kempe极大平面图猜想.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	许进	北京大学高可信软件技术教育部重点实验室	33	247	8.0	15.0