Polychromatic colorings of plane graphs
dc.contributor.author
Alon, Noga
dc.contributor.author
Berke, Robert
dc.contributor.author
Buchin, Kevin
dc.contributor.author
Buchin, Maike
dc.contributor.author
Csorba, Péter
dc.contributor.author
Shannigrahi, Saswata
dc.contributor.author
Speckmann, Bettina
dc.contributor.author
Zumstein, Philipp
dc.date.accessioned
2023-06-19T07:36:50Z
dc.date.available
2017-06-08T21:22:30Z
dc.date.available
2023-06-19T07:36:50Z
dc.date.issued
2008-06
dc.identifier.isbn
978-1-60558-071-5
en_US
dc.identifier.other
10.1145/1377676.1377734
en_US
dc.identifier.uri
http://hdl.handle.net/20.500.11850/14456
dc.description.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 Àý 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.
en_US
dc.language.iso
en
en_US
dc.publisher
Association for Computing Machinery
en_US
dc.title
Polychromatic colorings of plane graphs
en_US
dc.type
Conference Paper
dc.date.published
2008-06-09
ethz.book.title
SCG '08: Proceedings of the Twenty-fourth Annual Symposium on Computational Geometry
en_US
ethz.pages.start
338
en_US
ethz.pages.end
345
en_US
ethz.event
24th Annual Symposium on Computational Geometry (SCG 2008)
en_US
ethz.event.location
College Park, MD, USA
en_US
ethz.event.date
June 9-11, 2008
en_US
ethz.identifier.nebis
005646941
ethz.publication.place
New York, NY
en_US
ethz.publication.status
published
en_US
ethz.leitzahl
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02150 - Dep. Informatik / Dep. of Computer Science::02643 - Institut für Theoretische Informatik / Inst. Theoretical Computer Science::03672 - Steger, Angelika / Steger, Angelika::03457 - Welzl, Emo (emeritus) / Welzl, Emo (emeritus)
en_US
ethz.leitzahl.certified
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02150 - Dep. Informatik / Dep. of Computer Science::02643 - Institut für Theoretische Informatik / Inst. Theoretical Computer Science::03672 - Steger, Angelika / Steger, Angelika::03457 - Welzl, Emo (emeritus) / Welzl, Emo (emeritus)
ethz.date.deposited
2017-06-08T21:22:36Z
ethz.source
ECIT
ethz.identifier.importid
imp59364c3f2748b78487
ethz.ecitpid
pub:26078
ethz.eth
yes
en_US
ethz.availability
Metadata only
en_US
ethz.rosetta.installDate
2017-07-12T23:18:00Z
ethz.rosetta.lastUpdated
2024-02-03T00:15:43Z
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=Polychromatic%20colorings%20of%20plane%20graphs&rft.date=2008-06&rft.spage=338&rft.epage=345&rft.au=Alon,%20Noga&Berke,%20Robert&Buchin,%20Kevin&Buchin,%20Maike&Csorba,%20P%C3%A9ter&rft.isbn=978-1-60558-071-5&rft.genre=proceeding&rft_id=info:doi/10.1145/1377676.1377734&rft.btitle=SCG%20'08:%20Proceedings%20of%20the%20Twenty-fourth%20Annual%20Symposium%20on%20Computational%20Geometry
Files in this item
| Files | Size | Format | Open in viewer |
|---|---|---|---|
|
There are no files associated with this item. |
|||
Publication type
-
Conference Paper [34965]