Número Cromático

Definición 1:

Es el número de colores necesarios para el clásico óptimo (vértice) colorear el

gráfico, es decir, el menor número posible tal que sea posible colorear legalmente
vértices del gráfico colores. Está marcado con un símbolo. [1]

Definición 2:

Una coloración propia de G ocurre cuando se asignan colores a los vértices de G

de modo que si v i y v j  son adyacentes, entonces v i y v j tengan colores distintos
asignados. El número mínimo de colores necesarios para una coloración propia de
un grafo es lo que se conoce como número cromático del grafo. [2]

Definición 3:
El número cromático de una gráfica Ges 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-
coloreable (o bien, tiene una coloración propia con m colores). A este número se le
denota como χ (G), es decir, χ (G)=m. [3]

1
Teoría de Grafos. Reinhard Diestel. Pg 95
2
Número cromático. Universidad Técnica Nacional. https://www.frsn.utn.edu.ar/gie/av/nucro.html
3
Número cromático. Carlos Espinosa. https://es.scribd.com/document/364607450/Numero-Cromatico
Algoritmo para calcular números cromáticos

Algoritmo Voraz

Sea G un grafo no dirigido y S={a , b , c ,... } tal que |S|=n

Paso inicial:

Ordenar vértices en una lista {V 1 ,V 2 , V 3 , ... Vn}

Pasos de asignación de colores

P 1. Asignar a V 1el primer ¿ a

Pk . Coloración de Vk , K ≥ 2

Si se ha coloreado V 1 ,V 2 ,... , , Vk−1 con j colores, se asigna a Vkel color t, donde

t menor igual j+1es el mínimo color permitido para Vk teniendo en cuenta los
asignados a sus adyacentes. [4]

Ejemplo:

Conjuntos Maximalmente Independientes

4
Un algoritmo voraz para el numero cromático. Universidad Politécnica de Valencia.
https://www.youtube.com/watch?v=DyRh5UhtVvw

2
Definición 1:

Un conjunto independiente es un conjunto de vértices no adyacentes dos a dos.

Se denota por α(G) el tamaño de un conjunto independiente máximo. [5]

Definición 2:
Un conjunto independiente maximal es un conjunto independiente tal que,
añadiendo cualquier otro vértice al conjunto, este deja de ser independiente. El
Conjunto independiente maximal no debe confundirse con el máximo conjunto
independiente. El primero es un conjunto independiente que no está contenido en
ningún otro conjunto independiente mayor que él. [6]

Definición 3:
Un conjunto independiente I es maximal si para cualquier elemento x deV , el
conjunto I + {x } no es independiente. [7]

Figura: un conjunto independiente, un conjunto independiente maximal y un conjunto independiente

de cardinalidad máximo, de izquierda a derecha.

5
Clases de grafos y problemas de optimización
combinatoria. Flavia Bonomo. Pg 71
6
Conjunto independiente. LinkFang. https://es.linkfang.org/wiki/Conjunto_independiente
7
RECUBRIMIENTO POR VERTICES Y DOMINACION: ALGORITMOS SOBRE GRAFOS DE PROXIMIDAD Y GRAFOS
ALEATORIOS. Escuela Técnica Superior de Ingenieros Informáticos.
http://www.dma.fi.upm.es/personal/gregorio/grafos/web/recubrimiento_dominacion/webpage/pTeoria.ht
ml

3
Algoritmo para hallar Conjuntos maximalmente independientes

Algoritmo Voraz

En efecto, el problema de encontrar un conjunto independiente maximal puede

resolverse en tiempo polinomial mediante un simple algoritmo voraz. [8]

Ejemplo:

Grafo Únicamente Coloreable

Definición 1:
Se dice que G es k–coloreable si tiene al menos una k–coloración propia y que es
únicamente k–coloreable si tiene solamente una k–coloración propia distinguible.
Si Ges un grafo de n vértices y únicamente k coloreable, entonces tendrá k !
coloraciones diferentes no distinguibles entre sí. [9]

8
RECUBRIMIENTO POR VERTICES Y DOMINACION: ALGORITMOS SOBRE GRAFOS DE PROXIMIDAD Y GRAFOS
ALEATORIOS. Escuela Técnica Superior de Ingenieros Informáticos.
http://www.dma.fi.upm.es/personal/gregorio/grafos/web/recubrimiento_dominacion/webpage/pTeoria.ht
ml
9
Computación Simbólica. María Jose Zapata. P 17

4
Definición 2:
Un k-coloreo de un grafo G es una asignación de colores a sus vértices de manera
que no se usan más de k colores y no hay dos vértices adyacentes que reciban el
mismo color. [10]

Figura: Grafos de tipo 4-coloreo y 3-coloreo.

Definición 3:
Dada una función de coloración C de un grafo G, al conjunto de vértices que
tienen asignado el mismo color se le llama clase de color. Una k-coloración es una
función de coloración que no utiliza más de k colores; un grafo es k-coloreable si
admite una k-coloración; al mínimo valor k tal que G es k-coloreable se le llama el
número cromático. [11]

Algoritmo para hallar Grafos únicamente coloreables

Para hallar este tipo de grafos, existen numerosos algoritmos como lo son de tipo
secuencial básico, el de menor grado y el de Brelaz.

Algoritmo secuencial básico

Entrada: Una ordenación de los vértices de un grafo G.
Salida: Una coloración de los vértices.
Paso1: Asignar el color 1 al vértice v 1.

10
Clases de grafos y problemas de optimización
combinatoria. Flavia Bonomo. Pg 70
11
Solución a problemas de coloración clásicos utilizando Coloración de Gráficas Suaves. Pedro Lara, Miguel
Gutiérrez. Pg 2

5
Paso2: Si hemos coloreado v 1 , v 2, . , vk con j colores, asignamos a vk +1 el color t,
donde t &le j+1 es el mínimo color permitido para vk +1, según los colores ya
asignados a sus vecinos. [12]

Existen diferentes variantes del algoritmo secuencial básico, siempre basadas en

la ordenación de los vértices del grafo. Esto da lugar a numerosas variantes del
algoritmo secuencial.

Algoritmo de menor grado

Primero se elige vn como el vértice de menor grado, luego se elige vn−1 como el
vértice de menor grado en G {vn},y así se continúa recursivamente, examinando
los vértices de menor grado y eliminándolos del grafo. [13]

Algoritmo de Brelaz
Definimos el grado de color de un vértice v como el número de colores usados en
los vecinos de v. El orden en que iremos coloreando vértices depende del grado y
del grado de color.

Entrada: Un grafo G.
Salida: Una coloración de los vértices de G.
Paso 1: Ordenar los vértices en orden decreciente de grados.
Paso 2: Coloreamos un vértice de grado máximo con el color 1.
Paso 3: Seleccionamos un vértice, aún sin colorear, con grado de color máximo. Si
hay varios, elegimos el de grado máximo.
Paso 4: Colorear el vértice seleccionado en el paso 3 con el menor color posible.

12
Coloración de grafos. Escuela Técnica Superior de Ingenieros Informáticos.
http://www.dma.fi.upm.es/personal/gregorio/grafos/web/coloracion_listas_juego/html/Teoria.html
13
Coloración de grafos. Escuela Técnica Superior de Ingenieros Informáticos.
http://www.dma.fi.upm.es/personal/gregorio/grafos/web/coloracion_listas_juego/html/Teoria.html

6
Paso 5: Si todos los vértices se han coloreado, FIN. En caso contrario, volver al
paso 3. [14]

Conjunto Dominante Mínimo

Definición 1:
Un conjunto dominante D es minimal si para cualquier elemento xde D, el conjunto
D−{x } no es dominante. [15]

Definición 2:
Un γ −set deG es un conjunto dominante de tamaño mínimo. Es decir que D
domina el grafo G y para cualquier otro conjunto dominante D 0 se verifica
¿ D∨≤∨D 0∨. [16]

Definición 3:
Los conjuntos dominantes están estrechamente relacionados con los conjuntos
independientes: un conjunto independiente también es un conjunto dominante si y
solo si es un conjunto independiente máximo, por lo que cualquier conjunto
independiente máximo en un gráfico es necesariamente también un conjunto
dominante mínimo. [17]

Bibliografía

 Reinhard Diestel, 2000. Teoría de Grafos.

 Universidad Técnica Nacional, s.f.. Lecture 16: Número cromático. Disponible en:
https://www.frsn.utn.edu.ar/gie/av/nucro.html
14
Coloración de grafos. Escuela Técnica Superior de Ingenieros Informáticos.
http://www.dma.fi.upm.es/personal/gregorio/grafos/web/coloracion_listas_juego/html/Teoria.html
15
RECUBRIMIENTO POR VERTICES Y DOMINACION: ALGORITMOS SOBRE GRAFOS DE PROXIMIDAD Y GRAFOS
ALEATORIOS. Escuela Técnica Superior de Ingenieros Informáticos.
http://www.dma.fi.upm.es/personal/gregorio/grafos/web/recubrimiento_dominacion/webpage/pTeoria.ht
ml
16
Problemas de conjunto dominante en grafos. Universidad de Buenos Aires. Pg 10
17
Una nota sobre la complejidad del conjunto mínimo dominante Conjunto dominante. Journal of Discrete
Algorithms. Pg 4

7
 Carlos Espinosa, s.f.. Número cromático. Disponible en:
https://es.scribd.com/document/364607450/Numero-Cromatico
 Politécnica de Valencia. Un algoritmo voraz para el numero cromático. Disponible
en: https://www.youtube.com/watch?v=DyRh5UhtVvw
 Flavia Bonomo. Clases de grafos y problemas de optimización
 combinatoria. Disponible en:
https://www.matematica.uns.edu.ar/uma2016/material/curso%20UMA
%202016_fbonomo_handout.pdf
 LinkFang. Conjunto independiente. Disponible en:
https://es.linkfang.org/wiki/Conjunto_independiente
 Escuela Técnica Superior de Ingenieros Informáticos. RECUBRIMIENTO
POR VERTICES Y DOMINACION: ALGORITMOS SOBRE GRAFOS DE
PROXIMIDAD Y GRAFOS ALEATORIOS. Disponible en:
http://www.dma.fi.upm.es/personal/gregorio/grafos/web/recubrimiento_dominacion/we
bpage/pTeoria.html
 Computación Simbólica. María Jose Zapata. Solución a problemas de
coloración clásicos utilizando Coloración de Gráficas Suaves. Disponible
en: http://www.ugr.es/~anillos/textos/pdf/2016/ComputacionSimbolica.pdf
 Escuela Técnica Superior de Ingenieros Informáticos. Coloración de grafos.
Disponible en:
http://www.dma.fi.upm.es/personal/gregorio/grafos/web/coloracion_listas_juego/html/T
eoria.html
 Universidad de Buenos Aires. Problemas de conjunto dominante en grafos.
Disponible en:
http://cms.dm.uba.ar/academico/carreras/licenciatura/tesis/2012/Moyano_Veronica.pdf
 Journal of Discrete Algorithms. Una nota sobre la complejidad del conjunto
mínimo dominante Conjunto dominante. Disponible en:
https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.108.3223
