Kolorowanie wykresów minimalizujące liczbę kolorów w każdym niezależnym zestawie

11

Czy znane jest następujące roszczenie?

Twierdzenie : Dla każdego wykresu z wierzchołkami istnieje kolorystyka tak że każdy niezależny zestaw jest zabarwiony co najwyżej kolorami . $G$ $n$ $G$ $O(\sqrt{n})$

reference-request graph-colouring

— Igor Shinkar
źródło

11

Następujące twierdzenie jest mi znane, ale może się nie liczyć, ponieważ nie zostało opublikowane: Dowolny wykres na wierzchołkach może być zabarwiony, aby każdy indukowany podgrupa liczby chromatycznej co najwyżej użył co najwyżej kolorów , gdzie . $n$ $H$ $k$ $\chi(H)+B$ $B(B+1)\leq 2kn$

Jest to dowód indukcyjny; motywacją było rozważenie zabarwienia, które wykorzystuje niewiele kolorów nie tylko na wykresie, ale także na wszystkich indukowanych podrozdziałach. Nie znam jednak żadnych opublikowanych wyników.

— Aravind
źródło

10

Nie do końca o co prosisz, ale oto dolna granica - wykres, dla którego dowolne zabarwienie da niezależny zestaw pokolorowany przez kolorów: $\sqrt{n}$

Weź kopii $\sqrt{n}$ i połącz wszystkie wierzchołki z jednym wierzchołkiem. $K_{\sqrt{n}}$ $s$

Oczywiście każdy zestaw wierzchołków z różnychjest niezależnych i w każdej kopii $\sqrt{n}$ $K$ możesz znaleźć co najmniej jeden „nowy” kolor. $K_{\sqrt{n}}$

Ta dolna granica może być łatwo poprawiona do i jeżeli tak połączyćdo pojedynczego wierzchołka, ale pozostaje tylko $\sqrt{2n}$ $K_1,K_2,..$ kolory. $\Omega(\sqrt{n})$

— RB
źródło

Drugi przykład nie wydaje się poprawiać granicy. Myślę, że każdą IS można pokolorować za pomocą

. Na przykład dla n = 9,

jest zabarwiony na niebiesko,

na zielono i czerwono, a

na niebiesko, zielono i czerwono. Każdy maksymalny IS jest zabarwiony 2 kolorami, a nie 3.

2 \sqrt{2 n} / 3

$2\sqrt{2n}/3$

K_{1}

$K_1$

K_{2}

$K_2$

K_{3}

$K_3$

— użytkownik15669

Nie jestem pewny co masz na myśli. Drugi przykład poprawia związane, ale nie asymptotycznie. Możesz zbudować ~

wielkości kolorowe używa wierzchołek z

, od wierzchołka

z innym kolorem, i tak dalej (z

będziemy brać wierzchołek zabarwiony przez kolor, który jeszcze nie istnieje w naszym IS). I to odnosi się do każdej kolorystyki

.

2 \sqrt{n}

$2\sqrt n$

K_{1}

$K_1$

K_{2}

$K_2$

K_{i}

$K_i$

G

$G$

— RB

Również w twoim przykładzie IS, który obejmuje niebieski wierzchołek z

, zielony z

i czerwony z

jest zabarwiony 3 kolorami.

K_{1}

$K_1$

K_{2}

$K_2$

K_{3}

$K_3$

— RB

1

@RB dziękuję za przykład. drugi wykres przedstawia dolną granicę z grubsza

, jest to liczba taka, że

.

t \approx \sqrt{2 n}

$t \approx \sqrt{2n}$

1 + 2 + \dots + t = n

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

— Igor Shinkar

5

Co z następującym dowodem? Jeżeli , więc roszczenie jest oczywiście oczywiste. Załóżmy, że wręcz przeciwnie, i niechniezależnym zestawemo maksymalnej liczności. Kolorkolor 1 i rekursywnie koloru wykresz kolorów. Teraz, jeślijest niezależnym zbiór, należy rozważyć. Zgodnie z hipotezą indukcyjnąjest zabarwione co najwyżej $\alpha(G) \leq \sqrt{n}$ $I$ $G$ $\alpha$ $I$ $G - I$ $2,...,c$ $K$ $G$ $K' = K - I$ $K'$ kolory , a zatemjest zabarwione co najwyżej $\sqrt{n-\alpha}$ $K$ kolorów; nierówność zakłada, że $1+\sqrt{n-\alpha} \leq \sqrt{n}$ . $\alpha \geq \sqrt{n}$

— Super8
źródło

1

, ale ten dowód można prawdopodobnie zmodyfikować, aby pokazać, że dla dowolnego

każdy IS jest zabarwiony co najwyżej

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

(w żądaniu scalenia profilu) meta jest dobrym miejscem do opublikowania takiego żądania.

— Suresh Venkat