Star coloring bipartite planar graphs |
| |
Authors: | H A Kierstead André Kündgen Craig Timmons |
| |
Institution: | 1. Department of Mathematics, Arizona State University, Tempe, Arizona 85287‐1804;2. Department of Mathematics, California State University San Marcos, San Marcos, California 92096‐0001 |
| |
Abstract: | A star coloring of a graph is a proper vertex‐coloring such that no path on four vertices is 2‐colored. We prove that the vertices of every bipartite planar graph can be star colored from lists of size 14, and we give an example of a bipartite planar graph that requires at least eight colors to star color. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 1–10, 2009 |
| |
Keywords: | star coloring planar graphs |
|
|