科研之友
微信
新浪微博
Facebook
分享链接
摘要
A (k, d)-list assignment L of a graph is a function that assigns to each vertex v a list L(v) of at least k colors satisfying | L(x) boolean AND L(y)| <= d for each edge xy. An L-coloring is a vertex coloring pi such that p(v) is an element of L(v) for each vertex v and pi(x) not equal pi(y) for each edge xy. A graph G is (k, d)-choosable if there exists an L-coloring of G for every (k, d)-list assignment L. This concept is known as choosability with separation. In this paper, we will use Thomassen list coloring extension method to prove that planar graphs with neither 6-cycles nor adjacent 4-and 5-cycles are (3, 1)-choosable. This is a strengthening of a result obtained by using Discharging method which says that planar graphs without 5-and 6-cycles are (3, 1)-choosable.
