极大平面图的结构与着色理论

TaylorA

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

" G1 G! n1 \8 w


附件下载：

游客，如果您要查看本帖隐藏内容请回复

: x& _- s# D, a& o5 F$ L

刘工在呢

谢谢分享