Diferencia entre revisiones de «Coloración de grafos»
Contenido eliminado Contenido añadido
mSin resumen de edición |
→Vértice coloración: +cm |
||
Línea 20:
La terminología de usar colores para etiquetar vértices proviene del problema de colorear mapas. Las etiquetas como rojo o azul son solamente utilizadas cuando el número de colores es pequeño, y normalmente los colores están representados por los enteros {1, 2, 3, …}.
Una coloración que usa a lo más k colores se llama k-coloración (propia). El menor número de colores necesarios para colorear un grafo G se denota '''número cromático''' y se denota como χ(G). Un grafo que puede ser asignada una k-coloración (propia) es k-coloreable y es k-cromático si su número cromático es exactamente k. Un subconjunto de vértices asignados con el mismo color se llama una clase de color. Cada clase forma un conjunto independiente. Esto es, una k-coloración es lo mismo que una partición del conjunto de vértices en k conjuntos independientes, y los términos k-partito y k-coloreable tienen el mismo significado.
=== Polinomio cromático ===
| |||