Coloración de gráficos minimizando la cantidad de colores en cada conjunto independiente

11

¿Se conoce el siguiente reclamo?

Reclamación : Para cualquier gráfico con vértices existe una coloración de tal que cada conjunto independiente está coloreado como máximo por $G$ $n$ $G$ colores. $O(\sqrt{n})$

reference-request graph-colouring Igor Shinkar
fuente

11

Conozco la siguiente afirmación, pero es posible que no cuente porque no está publicada: cualquier gráfico en vértices puede colorearse de modo que cualquier subgrafía inducida de número cromático a lo sumo use como máximo colores , donde . $n$ $H$ $k$ $\chi(H)+B$ $B(B+1)\leq 2kn$

Esta es una prueba por inducción; la motivación era considerar los colores que usan pocos colores no solo en el gráfico sino también en todos los subgrafos inducidos. Sin embargo, no conozco ningún resultado publicado.

Aravind
fuente

10

No es exactamente lo que pide, pero aquí hay un límite inferior: un gráfico para el que cualquier coloración dará como resultado un conjunto independiente coloreado por colores: $\sqrt{n}$

Tomar copias de $\sqrt{n}$ , y conecta todos los vértices a un solo vértice. $K_{\sqrt{n}}$ $s$

Obviamente, cada conjunto de vértices de diferentes's son independientes, y en cada copia de $\sqrt{n}$ $K$ puede encontrar al menos un color "nuevo". $K_{\sqrt{n}}$

Este límite inferior se puede mejorar fácilmente a o así si conectamosa un solo vértice, pero solo permanece $\sqrt{2n}$ $K_1,K_2,..$ colores. $\Omega(\sqrt{n})$

RB
fuente

El segundo ejemplo no parece mejorar el límite. Creo que cualquier IS puede ser coloreado usando

. Por ejemplo, para n = 9,

está coloreado de azul,

de verde y rojo y

de azul, verde y rojo. Cualquier IS máximo está coloreado por 2 colores, no 3.

2 \sqrt{2 n} / 3

$2\sqrt{2n}/3$

K_{1}

$K_1$

K_{2}

$K_2$

K_{3}

$K_3$

user15669

No estoy seguro de lo que quieres decir. El segundo ejemplo mejora el límite, pero no asintóticamente. Puedes construir un ~

2 \sqrt{n}

$2\sqrt n$

K_{1}

$K_1$

K_{2}

$K_2$

K_{i}

$K_i$

G

$G$

K_{1}

$K_1$

K_{2}

$K_2$

K_{3}

$K_3$

1

t \approx \sqrt{2 n}

$t \approx \sqrt{2n}$

1 + 2 + \dots + t = n

$1+2+\dots + t = n$

5

$\alpha(G) \leq \sqrt{n}$ $I$ $G$ $\alpha$ $I$ $G - I$ $2,...,c$ $K$ $G$ $K' = K - I$ $K'$ $\sqrt{n-\alpha}$ $K$ $1+\sqrt{n-\alpha} \leq \sqrt{n}$ $\alpha \geq \sqrt{n}$

Súper 8
fuente

1

1 + \sqrt{n - \sqrt{n}} > \sqrt{n}

$1+\sqrt{n-\sqrt{n}}>\sqrt{n}$

ϵ > 0

$\epsilon>0$

(1 + ϵ) \sqrt{n} + C_{ϵ}

$(1+\epsilon)\sqrt{n}+C_\epsilon$

1

\sqrt{n}

$\sqrt{n}$

2 \sqrt{n}

$2 \sqrt{n}$

(en la solicitud de combinación de perfil) meta es un buen lugar para publicar dicha solicitud.

Suresh Venkat

Coloración de gráficos minimizando la cantidad de colores en cada conjunto independiente

Respuestas: