Geometria

Coloració de grafs i compatibilitats

Els grafs d’incompatibilitats converteixen restriccions per parelles en arestes, i les coloracions agrupen en una mateixa classe els vèrtexs compatibles. Per justificar un mínim, combinem una coloració amb pocs colors amb una cota inferior, com una clique o un cicle senar, i interpretem el resultat en el context.