Skip to main content
main-content

Tipp

Weitere Artikel dieser Ausgabe durch Wischen aufrufen

28.01.2020

Contrast in greyscales of graphs

Zeitschrift:
Journal of Combinatorial Optimization
Autoren:
Natalia de Castro, María A. Garrido-Vizuete, Rafael Robles, María Trinidad Villar-Liñán
Wichtige Hinweise

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Abstract

In this paper, we present the notion of greyscale of a graph, as a colouring of its vertices that uses colours from the continuous spectrum [0, 1]. Any greyscale induces another colouring by assigning to each edge the non-negative difference between the colours of its vertices. These edge colours are ordered in lexicographical increasing order and make up the contrast vector of the greyscale. The aim of the contrast problem for the given graph is to find the maximum contrast vector and the greyscales that give rise to it, namely the maximum contrast greyscales. The NP-completeness of this problem is stated by means of a functional relation between the chromatic number and the first component of the maximum contrast vector, named the lightest tone. Thus, we introduce the notion of lightest tone as a new invariant of the graph. The underlying structure of values of maximum contrast greyscales is addressed and we prove that they are linked by rational number sets, which are algorithmically determined. The restricted maximum contrast problem, that is, greyscales with prefixed extreme tones, is also defined and solved in polynomial time for different families of bipartite graphs.

Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten

Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 69.000 Bücher
  • über 500 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Umwelt
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Testen Sie jetzt 30 Tage kostenlos.

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 58.000 Bücher
  • über 300 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Testen Sie jetzt 30 Tage kostenlos.

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 50.000 Bücher
  • über 380 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Umwelt
  • Maschinenbau + Werkstoffe




Testen Sie jetzt 30 Tage kostenlos.

Literatur
Über diesen Artikel

Premium Partner

    Bildnachweise