Vertex partitioning of crown-free interval graphs (Q4944995)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 1420923
Language Label Description Also known as
default for all languages
No label defined
    English
    Vertex partitioning of crown-free interval graphs
    scientific article; zbMATH DE number 1420923

      Statements

      0 references
      0 references
      0 references
      20 January 2003
      0 references
      crown-free interval graphs
      0 references
      Vertex partitioning of crown-free interval graphs (English)
      0 references
      Bewiesen wird eine approximative Lösung der Färbung gewisser linearer Intervall-Mengen mit Hilfe beschreibender Graphen. Dazu werden bestimmte Partitionierungen der Graphen ohne Subgraph \(K[1,1,3]\) (``Krone''), welche einer Menge von Intervallen einer linear geordneten Menge entsprechen: Partitionierungen P, welche durch geordnete Folge von maximalen Sippen \(C[q]\) (cliques: Subgraphen entsprechend der Intervall-Ordnung) derart erzeugt werden, sodass P jeden Eckpunkt genau einmal überdeckt. Existenz wird durch algorithmische Konstruktion bewiesen. Stets ist P so möglich, dass jeder (gerichtete) Weg in höchstens vier Sippen von P erscheint. Bei Anwenden auf Intervall-Färbung von (Intervall-)Graphen ohne und mit Eckpunkt-Gewichten folgt daraus Existenz eines ``4-Approximations-Algorithmus'' und so eine approximative Lösung dieses allgemein NP-harten Färbungsproblems für Mengen mit den genannten Kronenfreien Graphen. For the entire collection see [Zbl 0929.00074].
      0 references

      Identifiers