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 , a total ordering L on V, and a vertex , let be the set of vertices 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 of G is the least k such that there is a total ordering L on V with for all vertices . 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 等数据库收录! |
|