Premium
Non‐rainbow colorings of 3‐, 4‐ and 5‐connected plane graphs
Author(s) -
Dvořák Zdeněk,
Král' Daniel,
Škrekovski Riste
Publication year - 2010
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20414
Subject(s) - combinatorics , mathematics , rainbow , vertex (graph theory) , plane (geometry) , discrete mathematics , graph , geometry , physics , quantum mechanics
We study vertex‐colorings of plane graphs that do not contain a rainbow face, i.e., a face with vertices of mutually distinct colors. If G is a 3 ‐connected plane graph with n vertices, then the number of colors in such a coloring does not exceed $\lfloor{{7n-8}\over {9}}\rfloor$ . If G is 4 ‐connected, then the number of colors is at most $\lfloor {{5n-6}\over {8}}\rfloor$ , and for n ≡3(mod8), it is at most $\lfloor{{5n-6}\over {8}}\rfloor-1$ . Finally, if G is 5 ‐connected, then the number of colors is at most $\lfloor{{25}\over{58}}{\rm n}-{{22} \over {29}}\rfloor$ . The bounds for 3 ‐connected and 4 ‐connected plane graphs are the best possible as we exhibit constructions of graphs with colorings matching the bounds. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 129–145, 2010