Informace o publikaci
MATCHINGS AND NONRAINBOW COLORINGS
| Autoři | |
|---|---|
| Rok publikování | 2009 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | SIAM Journal on Discrete Mathematics |
| Citace | |
| Doi | http://dx.doi.org/10.1137/060675927 |
| Klíčová slova | plane graphs; face-constrained coloring; nonrainbow coloring |
| Popis | 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*. |