Coloración de gráficos y Gráfico completo

Question

Si un grafo es k-colorable, ¿implica que debe tener un grafo k-completo como subgrafo? Por ejemplo, si un grafo tiene un número cromático = 5, ¿esto es suficiente para implicar que debe tener K5 como subgrafo?

Básicamente estoy tratando de resolver esta pregunta de MIT 6.042, conjunto de problemas 4 (2010):

Sea ($s_1$, $s_2$, ..., $s_n$) una secuencia arbitrariamente distribuida de los números 1, 2, ..., n 1, n. Por ejemplo, para n = 5, una secuencia arbitraria podría ser (5, 3, 4, 2, 1).

Define el grafo G=(V,E) de la siguiente manera:

1. V = {v1, v2, ..., vn}

2. e = (vi, vj ) E si cualquiera de las siguientes dos opciones se cumple:

   a. j = i + 1, para 1 ≤ i ≤ n - 1

   b. i = $s_k$, y j = $s_{k+1}$ para 1 ≤ k ≤ n1

Demuestra que este grafo es 4-colorable para cualquier (s1, s2, ..., sn).

Pista: Primero demuestra que un grafo en línea es 2-colorable. Ten en cuenta que un grafo en línea se define de la siguiente manera: El grafo de n nodos que contiene n-1 aristas en secuencia se conoce como el grafo de línea $L_n$

Mi enfoque: Tratando de demostrar por contradicción, asumiré que el grafo G no es 4-colorable, entonces requiere al menos 5 colores, esto implica que debe haber un K-5 como subgrafo en G (Aquí estoy usando una afirmación fuerte sobre la cual no estoy seguro). Luego mostraré que K-5 no es posible bajo las definiciones del grafo G, por lo tanto, una contradicción. ¿Es correcto este enfoque o hay uno mejor?

Answer 1

Considera el grafo $G$ con $7$ vértices $x_0,x_1,x_2,x_3,x_4,v,w$ y $16$ aristas: $x_0x_1$, $x_1x_2$, $x_2x_3$, $x_3x_4$, $x_4x_0$, $vx_0$, $vx_1$, $vx_2$, $vx_3$, $vx_4$, $wx_0$, $wx_1$, $wx_2$, $wx_3$, $wx_4$, $vw$. Este grafo no contiene un grafo completo $K_5$. Su número cromático es $5$: necesitarás $3$ colores para colorear correctamente los vértices $x_i$, y otro color para $v$, y otro color para $w$.

Para resolver el problema del MIT: Colorea el vértice $v_i$, donde $i=s_k$, con el color $0$ si tanto $i$ como $k$ son pares, $1$ si $i$ es par y $k$ es impar, $2$ si $i$ es impar y $k$ es par, $3$ si tanto $i$ como $k$ son impares.

Answer 2

He estado trabajando en este mismo problema y encontré esta pregunta anterior en este foro.

Aquí está el enlace al pdf del conjunto de problemas:

Conjunto de Problemas 4

Esta es la pregunta 6 (a). Aquí está cómo creo que se supone que debes responderla.

Primero coloreas los vértices del 1 al n con 2 colores, digamos azul y rojo, usando solo el primer conjunto de aristas como $(v_i,v_j)$ donde $j=i+1$, $1 \le i \le n-1$.

Entonces, el grafo desde el vértice 1 hasta el vértice n se ve así:

R-A-R-A-....

Ahora debes agregar las aristas $(v_{S_k},v_{S_{k+1}})$, $1\le k \le n-1$, una a la vez ajustando el color de $v_{S_{k+1}}$ para que sea diferente del color de los vértices a los que está conectado.

Pero solo hay tres posibles vértices conectados al nuevo vértice $v_{S_{k+1}}$. Como máximo, dos serían de la línea original y también $v_{S_k}$. Los dos de la línea original serían etiquetados como $v_{S_{k+1}-1}$ y $v_{S_{k+1}+1}$.

Así que, al agregar cada arista $(v_{S_k},v_{S_{k+1}})$ solo tienes que elegir como máximo un cuarto color para colorear $v_{S_{k+1}}$, un color diferente de $v_{S_k}$, $v_{S_{k+1}-1}$ y $v_{S_{k+1}+1}$.

Answer 3

Lemma1: Un grafo de líneas es 2 coloreable. La prueba es bastante sencilla.

Lemma2: El subgrafo que contiene los vértices impares (v1, v3, v5,...) forma uno o más grafos de líneas no intersectantes (no intersectantes en el sentido de que no hay nodos comunes en dos grafos de líneas) Prueba: Necesitamos demostrar que no existe un ciclo, y podemos usar esto junto con el hecho de que un nodo puede tener como máximo 2 aristas en el subgrafo

Lemma3: Lemma2 para el subgrafo con vértices pares.

Thm: El grafo es 4 coloreable Pf: Primero tomamos todos los vértices impares. Por el lemma 2 podemos colorear los vértices impares usando 2 colores (digamos Negro y Blanco). Ahora usando el lemma 3 podemos colorear los vértices pares usando 2 colores (diferentes de los impares) (digamos Rojo y Amarillo). Esto cubre todas las aristas desde un vértice impar a un vértice impar y un vértice par a un vértice par sin violar la coloración. Lo que queda son las aristas de un vértice impar a un vértice par. Esto claramente no viola la coloración de los vértices ya que un vértice impar puede tener ya sea negro/blanco y un vértice par puede tener ya sea rojo/amarillo. Por lo tanto, el grafo es 4 coloreable.