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

TaylorA

摘 要：设G 是一个k -色图，若G 的所有k -着色是 Kempe 等价的，则称G 为 Kempe 图。表征色数≥ 3 的 Kempe
图特征是一尚待解决难题。该文对极大平面图的 Kempe 等价性进行了研究，其主要贡献是：(1)发现导致两个 4-
1 J/ a& l/ F" l* }1 |6 W- W) V着色是 Kempe 等价的关键子图为 2-色耳，故对 2-色耳的特征进行了深入研究；(2)引入 σ -特征图，清晰地刻画了
一个图中所有 4-着色之间的关联关系，并深入研究了 σ -特征图的性质；(3)揭示了 4-色非 Kempe 极大平面图的
Kempe 等价类可分为树型，圈型和循环圈型，并指出这 3 种类型可同时存在于一个极大平面图的 4-着色集中；(4)
研究了 Kempe 极大平面图特征，给出了该类图的多米诺递推构造法，以及两个 Kempe 极大平面图猜想。
3 M5 m% K* }$ E4 Q+ e关键词：Kempe 极大平面图；Kempe 变换； σ -运算；Kempe 等价类； σ -特征图；2-色耳
6 w( {3 S( d" M( Z6 n5 _
: W& c# O7 H: E8 s) ?
2 K, `' q) t% i/ `
8 w8 S+ M# I0 y9 m' U4 ]& w
附件下载：

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

刘工在呢

谢谢分享