Coloration graphique minimisant le nombre de couleurs dans chaque ensemble indépendant

11

La revendication suivante est-elle connue?

Affirmation : Pour tout graphe à sommets, il existe une coloration de telle que chaque ensemble indépendant soit coloré par au plus $G$ $n$ $G$ couleurs. $O(\sqrt{n})$

reference-request graph-colouring Igor Shinkar
la source

11

La revendication suivante est connue de moi, mais peut ne pas compter car elle n'est pas publiée: Tout graphique sur sommets peut être coloré de sorte que tout sous-graphique induit de nombre chromatique au plus utilise au plus couleurs, où . $n$ $H$ $k$ $\chi(H)+B$ $B(B+1)\leq 2kn$

Ceci est une preuve par induction; la motivation était de considérer les colorations qui utilisent peu de couleurs non seulement sur le graphique mais aussi sur tous les sous-graphiques induits. Je ne connais cependant aucun résultat publié.

Aravind
la source

10

Pas tout à fait ce que vous demandez, mais voici une borne inférieure - un graphique pour lequel toute coloration se traduira par un ensemble indépendant coloré par couleurs: $\sqrt{n}$

Prenez exemplaires de $\sqrt{n}$ , et connectez tous les sommets à un seul sommet. $K_{\sqrt{n}}$ $s$

De toute évidence, chaque ensemble de sommets dedifférentssont indépendants, et dans chaque copie de $\sqrt{n}$ $K$ vous pouvez trouver au moins une "nouvelle" couleur. $K_{\sqrt{n}}$

Cette limite inférieure peut facilement être améliorée à ou si nous nous connectonsà un seul sommet, mais il ne reste que $\sqrt{2n}$ $K_1,K_2,..$ couleurs. $\Omega(\sqrt{n})$

RB
la source

Le deuxième exemple ne semble pas améliorer la borne. Je pense que tout IS peut être coloré en utilisant

. Par exemple, pour n = 9,

est coloré en bleu,

en vert et rouge et

en bleu, vert et rouge. Tout IS maximal est coloré par 2 couleurs, pas par 3.

2 \sqrt{2 n} / 3

$2\sqrt{2n}/3$

K_{1}

$K_1$

K_{2}

$K_2$

K_{3}

$K_3$

user15669

Je ne sais pas ce que tu veux dire. Le deuxième exemple améliore la borne, mais pas asymptotiquement. Vous pouvez construire 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}$

Super8
la source

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

(sur la demande de fusion de profil) meta est un bon endroit pour publier une telle demande.

Suresh Venkat

Coloration graphique minimisant le nombre de couleurs dans chaque ensemble indépendant

Réponses: