Publication details
MATCHINGS AND NONRAINBOW COLORINGS
Authors | |
---|---|
Year of publication | 2009 |
Type | Article in Periodical |
Magazine / Source | SIAM Journal on Discrete Mathematics |
Citation | |
Doi | http://dx.doi.org/10.1137/060675927 |
Keywords | plane graphs; face-constrained coloring; nonrainbow coloring |
Description | We show that the maximum number of colors that can be used in a vertex coloring of a cubic 3-connected plane graph G that avoids a face with vertices of mutually distinct colors (a rainbow face) is equal to (n)(2) vertical bar mu*- 2, where n is the number of vertices of G and mu* is the size of the maximum matching of the dual graph G*. |