Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
SPISTREŚCI
vii
5.2.2.
5.3.
5.3.1.
5.3.2.
5.4.
Wielomianowealgorytmyoptymalneiprzybliżone......................101
Uogólnieniaproblemusumychromatycznej.............................106
Problemsumacyjnegokolorowaniazkosztami..........................106
Sumamultichromatyczna..............................................107
Wybranezastosowaniasumychromatycznej............................108
Bibliografia..........................................................109
Rozdział6
Kontrastowekolorowaniegrafów
6.1.
6.2.
6.3.
6.4.
6.5.
6.6.
6.7.
6.7.1.
6.7.2.
6.7.3.
6.8.
6.8.1.
6.8.2.
6.8.3.
6.9.
RobertJanczewski
112
Rozpiętości..........................................................112
Zbioryodległościzakazanych.........................................115
Pokolorowaniakontrastowe............................................118
T-rozpiętościiliczbaT-chromatyczna.................................119
HomomorfizmyiT-grafy.............................................121
Oszacowaniaiwartościdokładne......................................123
Złożonośćobliczeniowa...............................................125
LiczbaT-chromatyczna...............................................125
T-rozpiętość.........................................................126
T-rozpiętośćkrawędziowa.............................................126
Algorytmyprzybliżone...............................................126
AlgorytmT-LF......................................................126
AlgorytmT-SL......................................................127
AlgorytmT-DSATUR................................................128
Zastosowania.........................................................128
Bibliografia..........................................................129
Rozdział7
Harmonicznekolorowaniegrafów
7.1.
7.2.
7.3.
7.4.
7.5.
MarekKubale
132
Wprowadzenie.......................................................133
Rodzinygrafówoznanejharmonicznejliczbiechromatycznej............135
Oszacowaniaharmonicznejliczbychromatycznejdlagrafówogólnych....139
Algorytmdegresywny................................................140
Zastosowania.........................................................142
Bibliografia..........................................................145
Rozdział8
Cyrkularnekolorowaniegrafów
8.1.
8.1.1.
8.1.2.
8.1.3.
8.1.4.
8.2.
AdamNadolski
147
Cyrkularnekolorowaniewierzchołków.................................147
Cyrkularnaliczbachromatycznaijejwłasności.........................147
Wyznaczenieχc(G)dlaniektórychklasgrafów.........................150
Cyrkularnekolorowaniegrafówobciążonych............................153
Zastosowaniecyrkularnegokolorowaniawierzchołków..................154
Cyrkularnekolorowaniekrawędzi......................................155
