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

TaylorA

摘 要：设G 是一个k -色图，若G 的所有k -着色是 Kempe 等价的，则称G 为 Kempe 图。表征色数≥ 3 的 Kempe
' A1 W5 U5 o% m# r$ U) s5 [  P图特征是一尚待解决难题。该文对极大平面图的 Kempe 等价性进行了研究，其主要贡献是：(1)发现导致两个 4-
着色是 Kempe 等价的关键子图为 2-色耳，故对 2-色耳的特征进行了深入研究；(2)引入 σ -特征图，清晰地刻画了
6 N4 Y$ @' q. E: h4 r) L+ r一个图中所有 4-着色之间的关联关系，并深入研究了 σ -特征图的性质；(3)揭示了 4-色非 Kempe 极大平面图的
Kempe 等价类可分为树型，圈型和循环圈型，并指出这 3 种类型可同时存在于一个极大平面图的 4-着色集中；(4)
# V+ Y+ e0 K  S* }& s# E$ u& I& U研究了 Kempe 极大平面图特征，给出了该类图的多米诺递推构造法，以及两个 Kempe 极大平面图猜想。
( ]2 J* A" [& @3 s( |  r9 N" j. [) C关键词：Kempe 极大平面图；Kempe 变换； σ -运算；Kempe 等价类； σ -特征图；2-色耳
9 N! `& [+ D  [6 l% @3 }& G. P

: |( }7 K; s$ N, K7 s2 h

- x- r7 X* W8 ?8 \' _& b6 r附件下载：

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

' r7 l. ~6 K( O3 `. [9 Z

刘工在呢

谢谢分享