广义Peterson图的列表边染色

摘要

列表边染色是边染色的加强版，对于图G的每个边给出一个可选用的颜色列表，染色时从列表中任选一种颜色，使相邻边的颜色互不相同就是列表边染色。近30年来染色理论研究的一个核心问题是列表边染色猜想，即每一个无环多重图的变色数等于列表边色数。该猜想已被广泛研究，其中最著名的结果是Galvill在1995年证明列表边染色猜想在二部多重图上成立。这篇文章着重在广义Peterson图上研究列表边染色，用做图的方法找到广义Petersoil图的边染色的染色规律，并运用著名的组合零点定理、积和式及其算法设计，将广义PetersOll图的列表边染色问题转化为多项式问题，从而证明了列表边染色猜想在广义Peterson图P（n，k）（k=2，3）上成立。