¿Por qué el número cromático del gráfico vacío es 1? Parece más natural que sea 0.
Respuesta
¿Demasiados anuncios?
The Amplitwist
Puntos
153
Dado que existe un único gráfico vacío de cada orden $n \geq 1$ Entiendo que "gráfico vacío" en su pregunta se refiere a "el gráfico vacío". $E_n$ en $n$ vértices para un número entero positivo $n$ ".
-
Como se necesita al menos un color para colorear los vértices de $E_n$ el número cromático de $E_n$ es al menos $1$ .
-
Como no hay aristas en $E_n$ todos los vértices pueden tener el mismo color sin problemas, por lo que el número cromático de $E_n$ es como máximo $1$ .
Por lo tanto, $\chi(E_n) = 1$ para todos $n \geq 1$ .
¿Qué pasa cuando $n = 0$ ? En este caso, tampoco hay vértices, por lo que el mapa vacío puede servir como una coloración válida de $E_0$ . Por lo tanto, tenemos $\chi(E_0) = 0$ .
Sin embargo, es discutible si se quiere clasificar $E_0$ como un gráfico vacío, o si se le debe dar un nombre diferente como " el gráfico nulo ". Resulta que $E_0$ es una excepción a varias definiciones para las que es un caso degenerado. Así que, en realidad, podría ser mejor evitar tener $E_0$ como un grafo válido en primer lugar; es decir, sería bueno exigir en la definición de un grafo que el conjunto de vértices por no vacío.
Véase el artículo de Harary y Read de 1974 en el que discuten los problemas con $E_0$ .
Referencias
- Harary, Frank; Read, Ronald C. ¿Es el gráfico nulo un concepto sin sentido?, Graphs and Combin, Proc. Capital Conf., Washington, D.C. 1973, Lect. Notes Math. 406, 37-44 (1974). ZBL0293.05101 .
