r-degenerierte Graphen
Die Degeneriertheit misst die inhärente Dünnbesetztheit eines Graphen und erlaubt eine schrittweise algorithmische Dekonstruktion.
- Formale Definition: Ein Graph
heißt -degeneriert ( ), wenn jeder seiner induzierten Untergraphen mindestens einen Knoten mit einem lokalen Grad von maximal besitzt: - Bezug zur Planarität: Da jeder planare Untergraph einen Knoten vom Grad
besitzen muss, sind alle planaren Graphen fundamental 5-degeneriert. - Färbungs-Algorithmus: Jeder
-degenerierte Graph lässt sich in linearer Zeit effizient mit maximal Farben färben ( ). Der Algorithmus sucht rekursiv den Knoten mit , entfernt ihn, färbt den Restgraphen und weist beim Backtracking die kleinste freie Farbe zu.