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 .n G O ( GnGO(n)

Igor Shinkar
źródło

Odpowiedzi:

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 .H k χ ( H ) + B B ( B + 1 ) 2 k nnHkχ(H)+BB(B+1)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:n

Weź kopiiKn i połącz wszystkie wierzchołki z jednym wierzchołkiems.Kns

Oczywiście każdy zestaw wierzchołków z różnychKjest niezależnych i w każdej kopiiKnK możesz znaleźć co najmniej jeden „nowy” kolor.Kn

Ta dolna granica może być łatwo poprawiona do i jeżeli tak połączyćK1,K2,. . do pojedynczego wierzchołka, ale pozostaje tylkoΩ(2nK1,K2,..kolory.Ω(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,K1jest zabarwiony na niebiesko,K2na zielono i czerwono, aK3na niebiesko, zielono i czerwono. Każdy maksymalny IS jest zabarwiony 2 kolorami, a nie 3.22n/3K1K2K3
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 zK1, od wierzchołkaK2z innym kolorem, i tak dalej (zKíbędziemy brać wierzchołek zabarwiony przez kolor, który jeszcze nie istnieje w naszym IS). I to odnosi się do każdej kolorystykiG. 2nK1K2KiG
RB
Również w twoim przykładzie IS, który obejmuje niebieski wierzchołek z , zielony z K 2 i czerwony z K 3 jest zabarwiony 3 kolorami. K1K2K3
RB
1
@RB dziękuję za przykład. drugi wykres przedstawia dolną granicę z grubsza , jest to liczba taka, że1+2++t=n. t2n1+2++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 niechbędęniezależnym zestawemGo maksymalnej licznościα. Kolor, żekolor 1 i rekursywnie koloru wykresG-Iz kolorów2,. . . ,c. Teraz, jeśliKjest niezależnym zbiórG, należy rozważyćK'=K-ja. Zgodnie z hipotezą indukcyjnąK'jest zabarwione co najwyżejα(G)nIGαIGI2,...,cKGK=KIK kolory α , a zatemKjest zabarwione co najwyżej1+nαK kolorów; nierówność zakłada, żeα1+nαn .αn

Super8
źródło
1
, ale ten dowód można prawdopodobnie zmodyfikować, aby pokazać, że dla dowolnegoϵ>0każdy IS jest zabarwiony co najwyżej(1+ϵ)1+nn>nϵ>0(1+ϵ)n+Cϵ
1
n2n
(w żądaniu scalenia profilu) meta jest dobrym miejscem do opublikowania takiego żądania.
Suresh Venkat