Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4652025 | Electronic Notes in Discrete Mathematics | 2013 | 6 Pages |
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