Article ID Journal Published Year Pages File Type
4652025 Electronic Notes in Discrete Mathematics 2013 6 Pages PDF
Abstract

For maximal planar graphs of order n⩾4, we prove that a vertex–coloring containing no rainbow faces uses at most colors, and this is best possible. The main ingredients in the proof are classical homological tools. By considering graphs as topological spaces, we introduce the notion of a null coloring, and prove that for any graph G a maximal null coloring f is such that the quotient graph G/f is a forest.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics