首页 | 本学科首页   官方微博 | 高级检索  
     


Minimum choosability of planar graphs
Authors:Huijuan Wang  Bin Liu  Ling Gai  Hongwei Du  Jianliang Wu
Affiliation:1.School of Mathematics and Statistics,Qingdao University,Qingdao,China;2.Department of Mathematics,Ocean University of China,Qingdao,China;3.School of Management,Shanghai University,Shanghai,China;4.Department of Computer Science and Technology,Harbin Institute of Technology Shenzhen Graduate School,Shenzhen,China;5.School of Mathematics,Shandong University,Jinan,China
Abstract:The problem of list coloring of graphs appears in practical problems concerning channel or frequency assignment. In this paper, we study the minimum number of choosability of planar graphs. A graph G is edge-k-choosable if whenever every edge x is assigned with a list of at least k colors, L(x)), there exists an edge coloring (phi ) such that (phi (x) in L(x)). Similarly, A graph G is toal-k-choosable if when every element (edge or vertex) x is assigned with a list of at least k colors, L(x), there exists an total coloring (phi ) such that (phi (x) in L(x)). We proved (chi '_{l}(G)=Delta ) and (chi ''_{l}(G)=Delta +1) for a planar graph G with maximum degree (Delta ge 8) and without chordal 6-cycles, where the list edge chromatic number (chi '_{l}(G)) of G is the smallest integer k such that G is edge-k-choosable and the list total chromatic number (chi ''_{l}(G)) of G is the smallest integer k such that G is total-k-choosable.
Keywords:
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号