View in EDS PDF Full Text

Polychromatic Colorings of Plane Graphs.

Saved in:
Bibliographic Details
Title: Polychromatic Colorings of Plane Graphs.
Authors: Alon, Noga1 nogaa@tau.ac.il, Berke, Robert2 berker@ethz.ch, Buchin, Kevin3 buchin@cs.uu.nl, Buchin, Maike3 maike@cs.uu.nl, Csorba, Péter4 pcsorba@win.tue.nl, Shannigrahi, Saswata5 saswata@tcs.tifr.res.in, Speckmann, Bettina4 speckman@win.tue.nl, Zumstein, Philipp6 zuphilip@inf.ethz.ch
Source: Discrete & Computational Geometry. Oct2009, Vol. 42 Issue 3, p421-442. 22p. 9 Diagrams.
Subjects: Polychromy, Central processing units, Dynamic random access memory, Computer input-output equipment, Computer storage device industry, Computer systems, Computer networks
Abstract: We show that the vertices of any plane graph in which every face is incident to at least g vertices can be colored by ⌊(3 g−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 ⌊(3 g+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 ℘ for k=2 and is $\mathcal{NP}$ -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 ℘, and for the others it is $\mathcal{NP}$ -complete. [ABSTRACT FROM AUTHOR]
Copyright of Discrete & Computational Geometry is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
FullText Links:
  – Type: pdflink
Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 42992871
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: Polychromatic Colorings of Plane Graphs.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Alon%2C+Noga%22">Alon, Noga</searchLink><relatesTo>1</relatesTo><i> nogaa@tau.ac.il</i><br /><searchLink fieldCode="AR" term="%22Berke%2C+Robert%22">Berke, Robert</searchLink><relatesTo>2</relatesTo><i> berker@ethz.ch</i><br /><searchLink fieldCode="AR" term="%22Buchin%2C+Kevin%22">Buchin, Kevin</searchLink><relatesTo>3</relatesTo><i> buchin@cs.uu.nl</i><br /><searchLink fieldCode="AR" term="%22Buchin%2C+Maike%22">Buchin, Maike</searchLink><relatesTo>3</relatesTo><i> maike@cs.uu.nl</i><br /><searchLink fieldCode="AR" term="%22Csorba%2C+Péter%22">Csorba, Péter</searchLink><relatesTo>4</relatesTo><i> pcsorba@win.tue.nl</i><br /><searchLink fieldCode="AR" term="%22Shannigrahi%2C+Saswata%22">Shannigrahi, Saswata</searchLink><relatesTo>5</relatesTo><i> saswata@tcs.tifr.res.in</i><br /><searchLink fieldCode="AR" term="%22Speckmann%2C+Bettina%22">Speckmann, Bettina</searchLink><relatesTo>4</relatesTo><i> speckman@win.tue.nl</i><br /><searchLink fieldCode="AR" term="%22Zumstein%2C+Philipp%22">Zumstein, Philipp</searchLink><relatesTo>6</relatesTo><i> zuphilip@inf.ethz.ch</i>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Discrete+%26+Computational+Geometry%22">Discrete & Computational Geometry</searchLink>. Oct2009, Vol. 42 Issue 3, p421-442. 22p. 9 Diagrams.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Polychromy%22">Polychromy</searchLink><br /><searchLink fieldCode="DE" term="%22Central+processing+units%22">Central processing units</searchLink><br /><searchLink fieldCode="DE" term="%22Dynamic+random+access+memory%22">Dynamic random access memory</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+input-output+equipment%22">Computer input-output equipment</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+storage+device+industry%22">Computer storage device industry</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+systems%22">Computer systems</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+networks%22">Computer networks</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: We show that the vertices of any plane graph in which every face is incident to at least g vertices can be colored by ⌊(3 g−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 ⌊(3 g+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 ℘ for k=2 and is $\mathcal{NP}$ -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 ℘, and for the others it is $\mathcal{NP}$ -complete. [ABSTRACT FROM AUTHOR]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of Discrete & Computational Geometry is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=42992871
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1007/s00454-009-9171-5
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 22
        StartPage: 421
    Subjects:
      – SubjectFull: Polychromy
        Type: general
      – SubjectFull: Central processing units
        Type: general
      – SubjectFull: Dynamic random access memory
        Type: general
      – SubjectFull: Computer input-output equipment
        Type: general
      – SubjectFull: Computer storage device industry
        Type: general
      – SubjectFull: Computer systems
        Type: general
      – SubjectFull: Computer networks
        Type: general
    Titles:
      – TitleFull: Polychromatic Colorings of Plane Graphs.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Alon, Noga
      – PersonEntity:
          Name:
            NameFull: Berke, Robert
      – PersonEntity:
          Name:
            NameFull: Buchin, Kevin
      – PersonEntity:
          Name:
            NameFull: Buchin, Maike
      – PersonEntity:
          Name:
            NameFull: Csorba, Péter
      – PersonEntity:
          Name:
            NameFull: Shannigrahi, Saswata
      – PersonEntity:
          Name:
            NameFull: Speckmann, Bettina
      – PersonEntity:
          Name:
            NameFull: Zumstein, Philipp
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 10
              Text: Oct2009
              Type: published
              Y: 2009
          Identifiers:
            – Type: issn-print
              Value: 01795376
          Numbering:
            – Type: volume
              Value: 42
            – Type: issue
              Value: 3
          Titles:
            – TitleFull: Discrete & Computational Geometry
              Type: main
ResultId 1