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


On the weak 2-coloring number of planar graphs
Institution:1. Department of Mathematics and Statistics, King Faisal University, Al-Ahsa 31982, Saudi Arabia;2. School of Mathematical and Statistical Sciences, Arizona State University, Tempe, AZ 85287, USA
Abstract:For a graph G=(V,E), a total ordering L on V, and a vertex vV, let Wcol2G,L,v] be the set of vertices wV for which there is a path from v to w whose length is 0, 1 or 2 and whose L-least vertex is w. The weak 2-coloring number wcol2(G) of G is the least k such that there is a total ordering L on V with |Wcol2G,L,v]|k for all vertices vV. We improve the known upper bound on the weak 2-coloring number of planar graphs from 28 to 23. As the weak 2-coloring number is the best known upper bound on the star list chromatic number of planar graphs, this bound is also improved.
Keywords:Weak 2-coloring number  Planar graph  Star chromatic number
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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