Null and non-rainbow colorings of maximal planar graphs
Por:
Montejano A., Arocha J.L.
Publicada:
1 ene 2013
Resumen:
For maximal planar graphs of order n=. 4, we prove that a vertex-coloring containing no rainbow faces uses at most ?2n-13? 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. © 2013 Elsevier B.V.
Filiaciones:
Montejano A.:
UMDI-Facultad de Ciencias, Universidad Nacional Autónoma de México, Querétaro, Mexico
Arocha J.L.:
Instituto de Matemáticas, Universidad Nacional Autónoma de México, D.F., Mexico
|