Teorema de De Bruijn–Erdős (teoria de grafs)

De Viquipèdia
Dreceres ràpides: navegació, cerca

En teoria de grafs, el teorema de De Bruijn-Erdős, demostrat per Nicolaas Govert de Bruijn i Paul Erdős el 1951,[1] estableix que, per a cada graf infinit G i enter finit k, es pot acolorir G amb k colors (de manera que cap parell de vèrtexs adjacents tingui el mateix color) si i només si tots els seus subgrafs finits es poden acolorir amb k colors. És a dir, cada graf k-crític (és a dir, cada graf que requereix k colors però per al qual tots els subgrafs requereixen un nombre menor de colors) ha de tenir un nombre finit de vèrtexs.

Referències[modifica | modifica el codi]

Bibliografia[modifica | modifica el codi]