Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Journal of Combinatorial Optimization
Erschienen in: Journal of Combinatorial Optimization 2/2016

01.02.2016

Two cases of polynomial-time solvability for the coloring problem

verfasst von: D. S. Malyshev

Erschienen in: Journal of Combinatorial Optimization | Ausgabe 2/2016

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

The complexity of the coloring problem is known for all hereditary classes defined by two connected 5-vertex forbidden induced subgraphs except 13 cases. We update this result by proving polynomial-time solvability of the problem for two of the mentioned 13 classes.
Vorheriger Artikel Dynamic monopolies and feedback vertex sets in cycle permutation graphs, generalized Petersen graphs and torus cordalis
Nächster Artikel An approximation algorithm for the partial vertex cover problem in hypergraphs

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

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

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

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

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

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




Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

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




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren
Literatur
Bhattacharya B, Hell P, Huang J (1996) A linear algorithm for maximum weight cliques in proper circular arc graphs. SIAM J Discrete Math 9:274–289MathSciNetCrossRefMATH
Dabrowski K, Lozin V, Raman R, Ries B (2012) Colouring vertices of triangle-free graphs without forests. Discrete Math 312:1372–1385MathSciNetCrossRefMATH
Dabrowski K, Golovach P, Paulusma D (2014) Colouring of graphs with Ramsey-type forbidden subgraphs. Theor Comput Sci 522:34–43MathSciNetCrossRefMATH
Golovach P, Paulusma D (2013) List coloring in the absence of two subgraphs. CIAC, 288–299
Gyarfas A (1987) Problems from the world surrounding perfect graphs. Zastos Mat Appl Math 3–4:413–441MathSciNet
Hoang C, Kaminski M, Lozin V, Sawada J, Shu X (2010) Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time. Algorithmica 57:74–81MathSciNetCrossRefMATH
Kral’ D, Kratochvil J, Tuza Z, Woeginger G (2001) Complexity of coloring graphs without forbidden induced subgraphs. Lecture Notes in Computer Science, vol 2204. Springer, New York, pp 254–262
Korpeilainen N, Lozin V, Malyshev D, Tiskin A (2011) Boundary properties of graphs for algorithmic graph problems. Theor Comput Sci 412:3544–3554
Lin MC, Szwarcfiter JL (2009) Characterizations and recognition of circular-arc graphs and subclasses: a survey. Discrete Math 309:5618–5635MathSciNetCrossRefMATH
Lozin V, Malyshev D (2014) Vertex coloring of graphs with few obstructions. Discrete Appl Math (accepted)
Maffray F, Preissmann M (1996) On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs. Discrete Math 162:313–317MathSciNetCrossRefMATH
Malyshev D (2012) Polynomial solvability of the independent set problem for one class of graphs with small diameter. Diskretnyi Analiz i Issledovanie Operatsii 19(4):66–72 [in Russian]MathSciNet
Metadaten
Titel
Two cases of polynomial-time solvability for the coloring problem
verfasst von
D. S. Malyshev
Publikationsdatum
01.02.2016
Verlag
Springer US
Erschienen in
Journal of Combinatorial Optimization / Ausgabe 2/2016
Print ISSN: 1382-6905
Elektronische ISSN: 1573-2886
DOI
https://doi.org/10.1007/s10878-014-9792-3

Weitere Artikel der Ausgabe 2/2016

Journal of Combinatorial Optimization 2/2016 Zur Ausgabe

OriginalPaper

Crossing edges and faces of line arrangements in the plane

OriginalPaper

Extremal polyomino chains with respect to general Randić index

OriginalPaper

Multi-depot vehicle routing problem with time windows under shared depot resources

OriginalPaper

Integral packing of branchings in capacitaded digraphs

OriginalPaper

Power domination with bounded time constraints

OriginalPaper

Verifying safety critical task scheduling systems in PPTL axiom system

Premium Partner

    Bildnachweise