Coloring plane graphs with independent crossings

Simple item page
dc.creatorKrál', Daniel
dc.creatorStacho, Ladislav
dc.date2008-11-17
dc.date.accessioned2026-07-07T10:18:51Z
dc.date.available2026-07-07T10:18:51Z
dc.descriptionWe show that every plane graph with maximum face size four whose 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.
dc.identifierhttps://arxiv.org/abs/0811.2702
dc.identifierhttp://arxiv.org/abs/0811.2702
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/174332
dc.subjectCombinatorics
dc.subject05C15 (Primary); 05C10 (Secondary)
dc.titleColoring plane graphs with independent crossings
dc.typetext

Files

Collections

arXiv