Skip to main content
main-content

Tipp

Weitere Artikel dieser Ausgabe durch Wischen aufrufen

26.03.2016 | Ausgabe 3/2017

Journal of Combinatorial Optimization 3/2017

A sufficient condition for planar graphs with girth 5 to be (1, 7)-colorable

Zeitschrift:
Journal of Combinatorial Optimization > Ausgabe 3/2017
Autoren:
Miao Zhang, Min Chen, Yiqiao Wang

Abstract

A graph G is \((d_1, d_2)\)-colorable if its vertices can be partitioned into subsets \(V_1\) and \(V_2\) such that in \(G[V_1]\) every vertex has degree at most \(d_1\) and in \(G[V_2]\) every vertex has degree at most \(d_2\). Let \(\mathcal {G}_5\) denote the family of planar graphs with minimum cycle length at least 5. It is known that every graph in \(\mathcal {G}_5\) is \((d_1, d_2)\)-colorable, where \((d_1, d_2)\in \{(2,6), (3,5),(4,4)\}\). We still do not know even if there is a finite positive d such that every graph in \(\mathcal {G}_5\) is (1, d)-colorable. In this paper, we prove that every graph in \(\mathcal {G}_5\) without adjacent 5-cycles is (1, 7)-colorable. This is a partial positive answer to a problem proposed by Choi and Raspaud that is every graph in \(\mathcal {G}_5\;(1, 7)\)-colorable?.

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

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

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

Weitere Artikel der Ausgabe 3/2017

Journal of Combinatorial Optimization 3/2017 Zur Ausgabe

Premium Partner

BranchenIndex Online

Die B2B-Firmensuche für Industrie und Wirtschaft: Kostenfrei in Firmenprofilen nach Lieferanten, Herstellern, Dienstleistern und Händlern recherchieren.

Whitepaper

- ANZEIGE -

Best Practices für die Mitarbeiter-Partizipation in der Produktentwicklung

Unternehmen haben das Innovationspotenzial der eigenen Mitarbeiter auch außerhalb der F&E-Abteilung erkannt. Viele Initiativen zur Partizipation scheitern in der Praxis jedoch häufig. Lesen Sie hier  - basierend auf einer qualitativ-explorativen Expertenstudie - mehr über die wesentlichen Problemfelder der mitarbeiterzentrierten Produktentwicklung und profitieren Sie von konkreten Handlungsempfehlungen aus der Praxis.
Jetzt gratis downloaden!

Bildnachweise