Tarea 12, Matemáticas discretas

Fecha de entrega: 6 de mayo

Problema 1

Muestra que los siguientes grafos no son 3-coloreables.

Problema 2

Considera n rectas genéricas en el plano, y considera el grafo formado por sus puntos de intersección y los segmentos de recta entre ellos. Muestra que este grafo es 3-coloreable.

Problema 3

Muestra el corolario visto en clase: si G es un grafo tal que cada subgrafo de G tiene al menos un vértice de grado d, entonces G es (d+1)-coloreable.

Problema 4

Sea G el grafo cuyos vértices corresponden a las aristas de $latex K_5$, y en el cual son adyancentes si dichas aristas tienen un vértice en común. Calcula el número cromático de G.

 Problema 5

1. Muestra que las regiones formadas por rectas en el plano son 2-coloreables.


2. Muestra que las regiones formadas por una curva cerrada en el plano (que se interseca a sí misma) son 2-coloreables.

Problema 6

Da un ejemplo de un mapa, con países no necesarimente conexos, que no sea 100-colorables.

Problema 7

1. Si cada cara de un mapa planar tiene un número par de aristas, entonces el grafo es bipartito.


2. Si cada vértice de un mapa planar tiene grado par, entonces las caras son 2-coloreables.