Archivo de July, 2019
La conjetura de Hedetniemi, sobre coloreado de grafos, es falsa
Un joven matemático ruso, Yaroslav Shitov, publicó en mayo un contraejemplo a la conjetura que dice que número cromático de GxH es el mínimo de los numeros cromaticos de los grafos G y H.
- el número cromático de un grafo es el mínimo número de colores necesario para colorear los vértices (cumpliendo que los dos vértices de una arista tienen colores distintos)
- G x H es el grafo producto cartesiano de G y H. Cada vértice es (i,j) donde i es vértice de G y j es vértice de H. Existe arista de (i,j) a (k,l) cuando (i,k) era arista en G y (j,l) era arista en H.
https://elpais.com/elpais/2019/07/01/ciencia/1561975026_683783.html
https://arxiv.org/abs/1905.02167