A note on entire choosability of plane graphs

作者：Dong Wei^*

来源：Discrete Applied Mathematics, 2012, 160(7-8): 1257-1261.

DOI：10.1016/j.dam.2011.12.014

• Entire coloring
• Plane graph
• List coloring

A plane graph is called entirely k-choosable if for any list assignment L such that vertical bar L(x)vertical bar= k for each x is an element of V(G) boolean OR E(G) boolean OR F(G), we can assign each element x a color from its list such that any two elements that are adjacent or incident receive distinct colors. Wang and Lih (2008) [5] conjectured that every plane graph is entirely (Delta + 4)-choosable and showed that the conjecture is true if Delta >= 12. In this note, we prove that (1) Every plane graph G with Delta >= 7 is entirely (Delta + 4)-choosable. (2) Every plane graph G with Delta >= 6 is entirely (Delta + 5)-choosable.

• 出版日期2012-5
• 单位南京晓庄学院