Problemet med att färga en graf med det minsta antalet färger är väl känt för att vara NPhard, även begränsad till k-färgbara grafer för konstant k 3. Å andra sidan är det känt att slumpmässiga k-färgbara grafer är lätta att k-färga. Algoritmerna för att färga slumpmässiga färgbara grafer kräver dock ganska hög kanttäthet. I detta papper presenterar vi algoritmer som färgar slumpmässigt genererade k-färgbara grafer för mycket lägre kant densiteter än tidigare metoder. Dessutom, för att studera en bredare variation av graffördelningar, presenterar vi också en modell av grafer som genereras av semi-random källan till Santha och Vazirani som ger en smidig övergång mellan de värsta-fall och slumpmässiga modeller. I denna modell genereras grafen av en \noisy motståndare"  på en motståndare vars beslut (om att infoga en viss kant eller inte) har någon liten (slumpmässig) sannolikhet för att bli omvänd. Vi visar att även för ganska låga bullernivåer, semi-random k-färgbara grafer kan vara optimalt färgade med hög sannolikhet. Denna förordning träder i kraft den tjugonde dagen efter det att den har offentliggjorts i Europeiska unionens officiella tidning.
Blum och Spencer REF initierade studien av semi-random modeller, och studerade problemet med graf färgning.
Coloring Random and Semi-Random k-Colorable Graphs
{'venue': 'J. Algorithms', 'journal': 'J. Algorithms', 'mag_field_of_study': ['Mathematics', 'Computer Science']}