Polychromatic colorings of plane graphs

N. Alon, R. Berke, K. Buchin, M. Buchin, P. Csorba, S. Shannigrahi, B. Speckmann, P. Zumstein

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

10 Citaten (Scopus)


We show that the vertices of any plane graph in which every face is of size at least g 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 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 3 colors in which all colors appear in every face is NP-complete even for graphs in which all faces are of size 3 or 4 only. If all faces are of size 3 this can be decided in polynomial time.
Originele taal-2Engels
TitelProceedings 24th Annual ACM Symposium on Computational Geometry (SoCG'08, College Park MD, USA, June 9-11, 2008)
Plaats van productieNew York NY
UitgeverijAssociation for Computing Machinery, Inc
ISBN van geprinte versie978-1-60558-071-5
StatusGepubliceerd - 2008


Duik in de onderzoeksthema's van 'Polychromatic colorings of plane graphs'. Samen vormen ze een unieke vingerafdruk.

Citeer dit