Polychromatic colorings of plane graphs

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

doi:10.1145/1377676.1377734

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/Congresprocedure › Conferentiebijdrage › Academic › peer review

9 Citaten (Scopus)

Samenvatting

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-2	Engels
Titel	Proceedings 24th Annual ACM Symposium on Computational Geometry (SoCG'08, College Park MD, USA, June 9-11, 2008)
Plaats van productie	New York NY
Uitgeverij	Association for Computing Machinery, Inc
Pagina's	338-345
ISBN van geprinte versie	978-1-60558-071-5
DOI's	https://doi.org/10.1145/1377676.1377734
Status	Gepubliceerd - 2008

Toegang tot document

10.1145/1377676.1377734

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

Citeer dit

@inproceedings{30322d3ff6e04e50954a2e05852121d8,

title = "Polychromatic colorings of plane graphs",

abstract = "We show that the vertices of any plane graph in which every face is of size at least g can be colored by (3g {\`A}{\'y} 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.",

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

year = "2008",

doi = "10.1145/1377676.1377734",

language = "English",

isbn = "978-1-60558-071-5",

pages = "338--345",

booktitle = "Proceedings 24th Annual ACM Symposium on Computational Geometry (SoCG'08, College Park MD, USA, June 9-11, 2008)",

publisher = "Association for Computing Machinery, Inc",

address = "United States",

}

Polychromatic colorings of plane graphs. / Alon, N.; Berke, R.; Buchin, K.; Buchin, M.; Csorba, P.; Shannigrahi, S.; Speckmann, B.; Zumstein, P.

Proceedings 24th Annual ACM Symposium on Computational Geometry (SoCG'08, College Park MD, USA, June 9-11, 2008). New York NY : Association for Computing Machinery, Inc, 2008. blz. 338-345.

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Conferentiebijdrage › Academic › peer review

TY - GEN

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 - 2008

Y1 - 2008

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

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

U2 - 10.1145/1377676.1377734

DO - 10.1145/1377676.1377734

M3 - Conference contribution

SN - 978-1-60558-071-5

SP - 338

EP - 345

BT - Proceedings 24th Annual ACM Symposium on Computational Geometry (SoCG'08, College Park MD, USA, June 9-11, 2008)

PB - Association for Computing Machinery, Inc

CY - New York NY

ER -