Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
1.2.KLASYCZNEKOLOROWANIEWIERZCHOŁKÓW
9
przybliżonegojestwogólnymprzypadkurównieżNP-trudne.Ostatnio
zostałpodanydowód,żeNP-trudnejest4-pokolorowanietakiegografu,
októrymwiemydodatkowo,iżjesttrójdzielny[16].Pozatymkolorowanie
klasycznepozostajetrudnenawetprzysilnychograniczeniachnałożonych
nagraforazliczbęużytychkolorów.Naprzykład,trudnajestodpowiedź
napytanie,czydasiępokolorowaćtrzemakoloramiwierzchołkigrafupla-
narnegoostopniunieprzekraczającym4[8].Jednakistniejąklasygrafów,
dlaktórychzgórymożnapodaćoptymalnąliczbękolorówlubznaleźć
ichpokolorowaniewrozsądnymczasie,np.grafyprzedziałowe[29].
Abyustalićoszacowanieliczbychromatycznej,należyzauważyć,że
liczbachromatycznagrafupustegowynosi1,natomiastdlagrafupełnego
rzędunwynosin.Stądwynikatrywialneograniczenieliczbychromatycz-
nejdowolnegografuG:
1<χ(G)<n.
Wceluuściśleniaoszacowaniadolnegonależyzauważyć,żekażdaklika
orozmiarzekwymagaużyciakkolorów.Stądoczywiście
ω(G)<χ(G).
Oszacowanietoniejestdokładne.Możnaskonstruowaćgrafyniezawie-
rająceklikiorozmiarze3(czylipodgrafuizomorficznegoztrójkątem),
tzn.takie,żeω(G)<3iwymagającedowolniedużejliczbykolorów.Au-
toremtakiejkonstrukcjijestnp.Mycielski[27].Ponadtoniejestznany
żadenefektywnysposóbwyznaczanialiczbyω(G),gdyżproblemtenjest
równieżNP-trudny.
Gorsze,alełatwedowyznaczeniaoszacowaniepodałGeller[9]wpo-
stacinierówności
n2−2m
n2
<χ(G).
Wkategoriioszacowańgórnychznanejestnastępująceoszacowanie:
χ(G)<∆(G)+1
(1.1)
Możnajestosunkowoprostoudowodnićprzezindukcjęwzględemlicz-
bywierzchołków.Oczywiściezachodzionodlagrafu1-wierzchołkowego.
NiechGbędziegrafemrzędun.JeżelizgrafuGusuniemywierzchołekυ
wrazzincydentnymikrawędziami,touzyskamygrafG/,dlaktóregoza-
chodzi∆(G/)<∆(G).Zzałożeniaindukcyjnegomamyχ(G/)<∆(G/)+1.
RozszerzeniepokolorowaniagrafuG/dlacałegografuGuzyskamy,na-
dająckolorwierzchołkowiυ.Ponieważwierzchołektenmastopieńco
