Coloring plane graphs with independent crossings |
| |
| Authors: | Daniel Král' Ladislav Stacho |
| |
| Institution: | 1. Faculty of Mathematics and Physics, Institute for Theoretical Computer Science (ITI), Charles University, Malostranské, Náměstí 25, 118 00 Prague, Czech Republic;2. Department of Mathematics, Simon Fraser University, 8888 University DR, Burnaby, BC, V5A 1S6 Canada |
| |
| Abstract: | We show that every plane graph with maximum face size four in which all faces of size four are vertex‐disjoint is cyclically 5‐colorable. This answers a question of Albertson whether graphs drawn in the plane with all crossings independent are 5‐colorable. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 184–205, 2010 |
| |
| Keywords: | planar graphs cyclic coloring crossing number chromatic number |
|
|
