Coloração de gráfico minimizando o número de cores em cada conjunto independente

11

A reivindicação a seguir é conhecida?

Reivindicação : Para qualquer gráfico com vértices existe uma coloração de tal que todo conjunto independente é colorido com no máximo $G$ $n$ $G$ cores. $O(\sqrt{n})$

reference-request graph-colouring Igor Shinkar
fonte

11

A seguinte afirmação é conhecida por mim, mas pode não contar porque não está publicada: Qualquer gráfico em vértices pode ser colorido para que qualquer subgrafo induzido do número cromático no máximo use no máximo cores, onde . $n$ $H$ $k$ $\chi(H)+B$ $B(B+1)\leq 2kn$

Esta é uma prova por indução; a motivação era considerar as cores que usam poucas cores, não apenas no gráfico, mas também em todos os subgráficos induzidos. Não estou ciente de nenhum resultado publicado.

Aravind
fonte

10

Não é exatamente o que você pede, mas aqui está um limite inferior - um gráfico para o qual qualquer coloração resultará em um conjunto independente colorido por cores: $\sqrt{n}$

Tome cópias de $\sqrt{n}$ e conecte todos os vértices a um único vértice. $K_{\sqrt{n}}$ $s$

Obviamente, todo conjunto de vértices dediferentessão independentes e em todas as cópias de $\sqrt{n}$ $K$ você pode encontrar pelo menos uma cor "nova". $K_{\sqrt{n}}$

Esse limite inferior pode ser facilmente aprimorado para ou assim se conectarpara um único vértice, mas permanece apenas $\sqrt{2n}$ $K_1,K_2,..$ cores. $\Omega(\sqrt{n})$

RB
fonte

O segundo exemplo não parece melhorar o limite. Eu acho que qualquer IS pode ser colorido usando

. Por exemplo, para n = 9,

é colorido em azul,

em verde e vermelho e

em azul, verde e vermelho. Qualquer máxima é é colorido por 2 cores, não 3.

2 \sqrt{2 n} / 3

$2\sqrt{2n}/3$

K_{1}

$K_1$

K_{2}

$K_2$

K_{3}

$K_3$

user15669

Não sei bem o que você quer dizer. O segundo exemplo melhora o limite, mas não assintoticamente. Você pode construir um ~

colorido IS de tamanho usando o vértice de

, o vértice de

com uma cor diferente e assim por diante (de

, pegaremos um vértice colorido por uma cor que ainda não existe em nosso IS). E isso vale para todos os coloração de

.

2 \sqrt{n}

$2\sqrt n$

K_{1}

$K_1$

K_{2}

$K_2$

K_{i}

$K_i$

G

$G$

RB

Além disso, no seu exemplo, o IS que inclui o vértice azul de

, o verde de

e o vermelho de

é colorido por 3 cores.

K_{1}

$K_1$

K_{2}

$K_2$

K_{3}

$K_3$

RB

1

@RB obrigado pelo exemplo. seu segundo gráfico fornece um limite inferior aproximadamente

, este é o número tal que

.

t \approx \sqrt{2 n}

$t \approx \sqrt{2n}$

1 + 2 + \dots + t = n

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

Igor Shinkar

5

E a prova a seguir? Se , então a alegação é óbvia. Suponha o contrário, e sejaum conjunto independente decom cardinalidade máxima. Corcom cor 1, cor e forma recursiva o gráficocom cores. Agora, seé um conjunto independente de, considere. Pela hipótese de indução,é colorido com no máximo $\alpha(G) \leq \sqrt{n}$ $I$ $G$ $\alpha$ $I$ $G - I$ $2,...,c$ $K$ $G$ $K' = K - I$ $K'$ cores e, portanto,é colorido com no máximo $\sqrt{n-\alpha}$ $K$ cores; a desigualdade é mantida pelo pressuposto de que $1+\sqrt{n-\alpha} \leq \sqrt{n}$ . $\alpha \geq \sqrt{n}$

Super8
fonte

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}$

(na solicitação de mesclagem de perfil) a meta é um bom lugar para postar essa solicitação.

Suresh Venkat

Coloração de gráfico minimizando o número de cores em cada conjunto independente

Respostas: