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

TaylorA

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

3 z/ S  L0 F* B4 r, G. ]' `( `

* R2 O4 X* g1 Z; J7 p) s0 W
附件下载：

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

: G0 ~  ^2 j- w* o$ W8 l& J

刘工在呢

谢谢分享