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*. |