Algoritmia para Problemas Difíciles

cuando los problemas se resisten …

Archivo de July, 2019

La conjetura de Hedetniemi, sobre coloreado de grafos, es falsa

Sin comentarios

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

 

 

Publicado por Elvira

July 6th, 2019 at 7:53 am

Publicado en Uncategorized