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

TaylorA

摘 要：设G 是一个k -色图，若G 的所有k -着色是 Kempe 等价的，则称G 为 Kempe 图。表征色数≥ 3 的 Kempe
图特征是一尚待解决难题。该文对极大平面图的 Kempe 等价性进行了研究，其主要贡献是：(1)发现导致两个 4-
着色是 Kempe 等价的关键子图为 2-色耳，故对 2-色耳的特征进行了深入研究；(2)引入 σ -特征图，清晰地刻画了
一个图中所有 4-着色之间的关联关系，并深入研究了 σ -特征图的性质；(3)揭示了 4-色非 Kempe 极大平面图的
: J8 S1 c" g4 X: K- f" f# P  o) DKempe 等价类可分为树型，圈型和循环圈型，并指出这 3 种类型可同时存在于一个极大平面图的 4-着色集中；(4)
研究了 Kempe 极大平面图特征，给出了该类图的多米诺递推构造法，以及两个 Kempe 极大平面图猜想。
( w4 ?  O+ {; y; C6 a关键词：Kempe 极大平面图；Kempe 变换； σ -运算；Kempe 等价类； σ -特征图；2-色耳
# \7 a' T- }+ B' z' ^
* W" f( e! P" O- E9 X3 O

) p! F/ C7 V  ?! h6 e
$ `2 R) p. F/ P7 V附件下载：

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

4 I$ m" g- g% r

刘工在呢

谢谢分享