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


The list L(2,1)-labeling of planar graphs
Authors:Haiyang Zhu  Lianying Miao  Sheng Chen  Xinzhong Lü  Wenyao Song
Institution:1. Department of Flight Support Command, Air Force Logistics College, Xuzhou 221000, PR China;2. College of Sciences, China University of Mining and Technology, Xuzhou 221008, PR China;3. Department of Mathematics, Harbin Institute of Technology, Harbin 150001, PR China;4. Department of Mathematics, Zhejiang Normal University, Jinhua 321004, PR China
Abstract:Let N be the set of all positive integers. A list assignment of a graph G is a function L:V(G)?2N that assigns each vertex v a list L(v) for all vV(G). We say that G is L-(2,1)-choosable if there exists a function ? such that ?(v)L(v) for all vV(G), |?(u)??(v)|2 if u and v are adjacent, and |?(u)??(v)|1 if u and v are at distance 2. The list-L(2,1)-labeling number λl(G) of G is the minimum k such that for every list assignment L={L(v):|L(v)|=k,vV(G)}, G is L-(2,1)-choosable. We prove that if G is a planar graph with girth g8 and its maximum degree Δ is large enough, then λl(G)Δ+3. There are graphs with large enough Δ and g8 having λl(G)=Δ+3.
Keywords:Planar graphs  Corresponding author  
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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