Färbung von zufälligen und semi-zufälligen k-färbbaren Graphen

Das Problem, einen Graphen mit der minimalen Anzahl von Farben zu färben, ist wohl bekannt, dass es NP-schwer ist, selbst beschränkt auf k-färbbare Graphen für konstantes k ≥ 3. Auf der anderen Seite ist bekannt, dass zufällige k-färbbare Graphen einfach k-färbbar sind. Die Algorithmen zur Färbung von zufälligen k-färbbaren Graphen erfordern jedoch eine relativ hohe Kantenintensität. In diesem Papier präsentieren wir Algorithmen, die zufällig generierte k-färbbare Graphen für viel niedrigere Kantenintensitäten als frühere Ansätze färben. Darüber hinaus stellen wir zur Untersuchung einer breiteren Vielfalt von Graphverteilungen auch ein Modell von Graphen vor, die von der semi-zufälligen Quelle von Santha und Vazirani (M. Santha und U. V. Vazirani, J. Comput. System Sci.33 (1986), 75-87) erzeugt werden, welches einen sanften Übergang zwischen den schlechtesten und zufälligen Modellen bietet. In diesem Modell wird der Graph von einem "rauschenden Gegner" erzeugt - einem Gegner, dessen Entscheidungen (ob eine bestimmte Kante eingefügt werden soll oder nicht) mit einer kleinen (zufälligen) Wahrscheinlichkeit umgekehrt werden können. Wir zeigen, dass selbst bei ziemlich niedrigen Rauschraten semi-zufällige k-färbbare Graphen mit hoher Wahrscheinlichkeit optimal gefärbt werden können.