Ejercicio · ZW-COLORACION-DE-GRAFOS-009 · ★★★ Avanzado
Sea \(\Delta\) el grado máximo de un grafo \(G\). ¿Qué afirmación es verdadera para todo grafo?
Elige una opción.
Ver respuesta
- A. \(G\) se puede colorear con \(\Delta+1\) colores
Explicación
Un coloreo voraz siempre encuentra color libre entre \(\Delta+1\), pues un vértice tiene a lo más \(\Delta\) vecinos. \(K_4\) refuta «se puede colorear con \(\Delta\) colores» (necesita 4 con \(\Delta=3\)) y un camino refuta «necesita al menos \(\Delta+1\) colores» y «necesita tantos colores como vértices».
Repasa el concepto: Coloración de grafos
Una coloración propia \(c\) con \(k\) colores de un grafo \(G=(V,E)\) asigna a cada vértice uno de los colores \(1,\dots,k\) sin que dos vértices adyacentes compartan color.
\[c:V\to\{1,\dots,k\},\qquad c(u)\neq c(v)\ \text{ si } \{u,v\}\in E\]
Más ejercicios de coloración de grafos
- ZW-COLORACION-DE-GRAFOS-001 ¿Cuántos colores necesita como mínimo una coloración propia del grafo completo K_5?
- ZW-COLORACION-DE-GRAFOS-002 ¿Cuántos colores necesita como mínimo un grafo que tiene al menos una arista?
- ZW-COLORACION-DE-GRAFOS-003 ¿Cuántos colores necesita como mínimo el ciclo C_7 (7 vértices)?
- ZW-COLORACION-DE-GRAFOS-004 ¿Cuántos colores necesita como mínimo el ciclo C_8?
- ZW-COLORACION-DE-GRAFOS-005 El grafo tiene vértices 1,2,3,4 y aristas \1,2\,\2,3\,\1,3\,\3,4\. ¿Cuál es una coloración propia?
- ZW-COLORACION-DE-GRAFOS-006 La rueda W_5 es un ciclo C_5 más un vértice central unido a los 5 vértices del ciclo. ¿Cuántos colo…
- ZW-COLORACION-DE-GRAFOS-007 ¿De cuántas formas se puede colorear un camino de 4 vértices con 3 colores disponibles, de modo que…
- ZW-COLORACION-DE-GRAFOS-008 El grafo de Petersen tiene 10 vértices, todos de grado 3, y contiene ciclos de longitud 5. ¿Cuál es…