Monotone Grapheigenschaft

Als monotone Grapheigenschaft oder monotone Grapheneigenschaft bezeichnet man in der Graphentheorie eine Eigenschaft von Graphen, die für jeden Teilgraphen eines Graphen gilt, sobald der Graph selbst diese Eigenschaft hat.

Beispiele monotoner Eigenschaften

• Planarität
• Bipartitheit
• Dreiecksfreiheit

Eigenschaften

Nach dem Satz von Bollobás besitzt jede monotone Grapheneigenschaft eine Schwellenfunktion.

Literatur

• Béla Bollobás: Hereditary and Monotone Properties of Graphs. doi:10.1007/978-3-642-60406-5_7
• Ehud Friedgut, Gil Kalai: Every monotone graph property has a sharp threshold
• Noga Alon, Asaf Shapira: Every monotone graph property is testable
• B. Bollobás, A. G. Thomason: . In: . Band 7, Nr. 1, 1. März 1987, ISSN 1439-6912, S. 35–38, doi:10.1007/BF02579198