(3, 1)? -choosability of planar graphs

主讲教师:陈敏 人气:1543 更新时间: 2017年06月24日
摘要:An (L, d) ? -coloring is a mapping π that assigns a color π(v) ∈ L(v) to each vertex v ∈ V (G) so that at most d neighbors of v receive color π(v). A graph G is said to be (k, d) ? -choosable if it admits an (L, d) ? -coloring for every list assignment L with |L(v)| ≥ k for all v ∈ V (G). In this talk, firstly, I will show some known results on improper list coloring of (planar) graphs with some restrictions. Then, I will give a short proof of our recent result which says that every planar graph without adjacent triangles and 6-cycles is (3, 1)? -choosable. This partially answers the question proposed by Xu and Zhang that every planar graphs without adjacent triangles is (3, 1)? - choosable. This is joint work with Andr′e Raspaud and Weifan Wang. Keyword: Planar graphs; Improper choosability; Cycle


手动翻阅 (大图)


地址:安徽省合肥市金寨路96号;邮编:230026。TEL:+86-551-63602922;E-mail:wlkt@ustc.edu.cn。 课件总访问人次:19169812