Coloring plane graphs with independent crossings

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

Published by

Original source : http://dx.doi.org/10.1002%2Fjgt.20448...