TY - JOUR

T1 - Polychromatic colorings of plane graphs

AU - Alon, N.

AU - Berke, R.

AU - Buchin, K.

AU - Buchin, M.

AU - Csorba, P.

AU - Shannigrahi, S.

AU - Speckmann, B.

AU - Zumstein, P.

PY - 2009

Y1 - 2009

N2 - We show that the vertices of any plane graph in which every face is incident to at least g vertices can be colored by ¿(3g-5)/4¿ colors so that every color appears in every face. This is nearly tight, as there are plane graphs where all faces are incident to at least g vertices and that admit no vertex coloring of this type with more than ¿(3g+1)/4¿ colors. We further show that the problem of determining whether a plane graph admits a vertex coloring by k colors in which all colors appear in every face is in P for k=2 and is -complete for k=3,4. We refine this result for polychromatic 3-colorings restricted to 2-connected graphs which have face sizes from a prescribed (possibly infinite) set of integers. Thereby we find an almost complete characterization of these sets of integers (face sizes) for which the corresponding decision problem is in P, and for the others it is -complete.

AB - We show that the vertices of any plane graph in which every face is incident to at least g vertices can be colored by ¿(3g-5)/4¿ colors so that every color appears in every face. This is nearly tight, as there are plane graphs where all faces are incident to at least g vertices and that admit no vertex coloring of this type with more than ¿(3g+1)/4¿ colors. We further show that the problem of determining whether a plane graph admits a vertex coloring by k colors in which all colors appear in every face is in P for k=2 and is -complete for k=3,4. We refine this result for polychromatic 3-colorings restricted to 2-connected graphs which have face sizes from a prescribed (possibly infinite) set of integers. Thereby we find an almost complete characterization of these sets of integers (face sizes) for which the corresponding decision problem is in P, and for the others it is -complete.

U2 - 10.1007/s00454-009-9171-5

DO - 10.1007/s00454-009-9171-5

M3 - Article

VL - 42

SP - 421

EP - 442

JO - Discrete and Computational Geometry

JF - Discrete and Computational Geometry

SN - 0179-5376

IS - 3

ER -