(3, 1)? -choosability of planar graphs

主讲教师:陈敏 人气:1203 更新时间: 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
目录
互动讨论

课堂PPT

手动翻阅 (大图)
1/31

相关视频

中国科学技术大学研究生网络课堂试运行版,版权属于中国科学技术大学研究生院。
本网站所有内容属于中国科学技术大学,未经允许不得下载传播。
地址:安徽省合肥市金寨路96号;邮编:230026。TEL:+86-551-63602922;E-mail:wlkt@ustc.edu.cn。 课件总访问人次:17094943