Reducir una gráfica sin bajar su número cromático

Mientras intentaba encontrar un algoritmo para reducir un gráfico sin reducir su número cromático, hice el siguiente algoritmo (pero no estoy seguro de si funciona):

  1. Dado un gráfico (simple) GRAMO , busca subgrafos de metro ( metro ≥ 2 ) vértices, que son isomorfos a k metro menos un borde, y cuyo borde vacío (digamos, mi = ( v 1 , v 2 ) ) todavía está sin completar GRAMO , es decir mi ∉ mi ( GRAMO ) . Elija tal subgrafo con máxima metro y luego identificar v 1 y v 2 . Después de reducir algunas aristas múltiples a aristas simples, obtenemos un nuevo gráfico simple GRAMO ′ cuyo número de vértices es uno menos que el de GRAMO .
  2. Repita el #1 hasta que no haya tal subgrafo.

Llamemos a este algoritmo "primer plegado de la dimensión más alta (HDFF)". Me pregunto si HDFF siempre nos da k x ( GRAMO ) , dónde x ( GRAMO ) es el número cromático de GRAMO , y k norte es el gráfico completo en norte vértices.

No entiendo muy bien el paso 1, ¿quieres decir que eliminas cualquiera de los dos? v 1 o v 2 y todos los bordes incidentes desde GRAMO ?
@lattice No. Me refiero a "identificar" (= pegar) dos vértices, sin eliminar ninguno de ellos.
Oh bien, ahora lo tengo. Buena pregunta, y estoy de acuerdo con la segunda respuesta de Mosquite.

Respuestas (2)

Me lo imaginé. Su algoritmo no conserva el número cromático (sin embargo, no puede reducir el número cromático) y esta vez encontré una razón correcta.

Considere el gráfico, GRAMO . los vértices v 1 , v 2 , X 1 , X 2 de GRAMO crear un k 4 con el borde entre v 1 y v 2 desaparecido. El más largo k metro − mi en este gráfico tiene metro = 3 y uno está dado por X 1 , X 2 , v 1 , v 2 .

Aplicando (1) a este gráfico con v 1 y v 2 identificado produce un gráfico con un inducido k 5 subgrafo Por lo tanto tiene número cromático al menos 5. Sin embargo, GRAMO tiene el número cromático 4 como podemos ver en el coloreado de la figura de GRAMO .

Bonito ejemplo. Gracias.

Su algoritmo dará como resultado un gráfico completo, pero creo que no conserva el número cromático. El gráfico de Grötzsch , es el gráfico más pequeño sin triángulos y número cromático 4. El subgráfico inducido más grande del gráfico de Grötzsch que es k metro menos un borde tiene metro = 3 . Aplicar (1) de su algoritmo a cualquier par de vértices no adyacentes del gráfico de Grötzsch dará como resultado un gráfico que no tiene triángulos y es más pequeño que el gráfico de Grötzsch y, por lo tanto, tiene un número cromático diferente.

EDITAR: Esto está mal. Hay triángulos en el gráfico resultante después de aplicar (1). Veré esto un poco más tarde.

Parece que no TODOS los pares de vértices no adyacentes del gráfico de Grötzsch darán como resultado un gráfico que no tenga triángulos... ¿Puedes especificar un par? No puedo encontrar uno fácilmente.
El gráfico de Grötzsch en sí ya no tiene triángulos, por lo que aplicar (1) (posiblemente varias veces) siempre dará como resultado un gráfico sin triángulos, ya que (si obtuve (1) correctamente) solo está eliminando vértices y bordes. Además, todos los vértices no adyacentes están conectados a través de un camino de longitud 2, lo que produce un subgrafo que es k 3 menos un borde, por lo que es posible aplicar (1) al menos una vez. Dado que el gráfico de Grötzsch es el gráfico más pequeño sin triángulos y número cromático 4 , aplicando (1) una vez dará un gráfico con un número cromático más pequeño. Por lo tanto, HDFF no conduce a k x ( GRAMO ) en este caso.
Vaya, en una inspección más cercana veo que hay un triángulo en el gráfico resultante. Culpa mía.
Reducir una gráfica sin bajar su número cromático
RespuestasAquíPolítica de privacidad1y, 0v