Número cromático
31.01.2024
El número cromático de una gráfica G es la menor cantidad de colores necesarios para colorear sus vértices sin que dos vértices vecinos (unidos por una arista) tengan el mismo color. O más formalmente, es el menor entero m tal que G es más coloreable (o bien, tiene una coloración propia con m colores). A este número se le denota como χ(G), es decir, χ(G)=m.
El número cromático de un grafo G, χ(G), es el número mínimo de colores necesarios en una coloración factible de G. Una coloración factible de G usando exactamente χ(G) colores se considera óptima.