Molloy M.S., Reed B. — Graph Colouring and the Probabilistic Method :: Электронная библиотека попечительского совета мехмата МГУ

Главная Ex Libris Книги Журналы Статьи Серии Каталог Wanted Загрузка ХудЛит Справка Поиск по индексам Поиск Форум

Авторизация

Поиск по указателям

Molloy M.S., Reed B. — Graph Colouring and the Probabilistic Method

Обсудите книгу на научном форуме

Нашли опечатку?
Выделите ее мышкой и нажмите Ctrl+Enter

Название: Graph Colouring and the Probabilistic Method

Авторы: Molloy M.S., Reed B.

Аннотация:

Over the past decade, many major advances have been made in the field of graph colouring via the probabilistic method. This monograph provides an accessible and unified treatment of these results, using tools such as the Lovasz Local Lemma and Talagrand's concentration inequality.
The topics covered include: Kahn's proofs that the Goldberg-Seymour and List Colouring Conjectures hold asymptotically; a proof that for some absolute constant C, every graph of maximum degree Delta has a Delta+C total colouring; Johansson's proof that a triangle free graph has a O(Delta over log Delta) colouring; algorithmic variants of the Local Lemma which permit the efficient construction of many optimal and near-optimal colourings.
This begins with a gentle introduction to the probabilistic method and will be useful to researchers and graduate students in graph theory, discrete mathematics, theoretical computer science and probability.

Язык:

Рубрика: Математика/

Статус предметного указателя: Готов указатель с номерами страниц

ed2k: ed2k stats

Год издания: 2002

Количество страниц: 326

Добавлена в каталог: 02.05.2008

Операции: Положить на полку | Скопировать ссылку для форума | Скопировать ID

Предметный указатель

(a,b)-tree      297
Activity      247
Adjacent      3
Alon      34 41 61 224 225 242 301
Appel      9
ASSIGN      84
Azuma      94
Azuma's inequality      43 79 91—94 100 103 205
Bad pair of matchings      261
Baik      83
Beck      29 285 291 295 301—304
Behzad      7 55
Berge      8
bernoulli      24
Beutelspacher      94
Beutelspacher — Hering Conjecture      94 155 157
Big clique      96
Bollobas      46
Borodin      94 107
Brooks      6
Brooks' Theorem      6 7 10 12 13 87 89 94 96 98 107 165 169
Burgess      1
Caitlin      45
candidate      192 2
Catlin      107
Chemoff Bound      43 44 46 55 56 58 63 64 71 74 75 79 50 82 91 138 144
Chromatic index      3
Chromatic number      3
CLIQUE      5
Clique number      5
Cochromatic number      34
Colour class      3
Colouring acceptable      11
Colouring edge      3 225 265
Colouring edge, acyclic      225
Colouring fractional      239 245 246
Colouring fractional edge      239 241
Colouring fractional total      239
Colouring k-cotouring      3
Colouring number      12 31 41
Colouring partial      4
Colouring partition respecting      196
Colouring strong edge      87
Colouring total      3 55 58 67—70 74 185 195
Complete a partial colouring      4 180
Conditional expectation      19
Conditional probability      16
conflicts      57
contract      8
Coupon collector's problem      109
Czumaj      303 304
d-regular      10
Degree      5
Deift      83
Dense decomposition      158 160—162 166 168 169 171 175 180 182 195 196
Dense matchable      164
Dense set      157 158
Dinitz      11 12
Dirac      9
Discrepancy      44 304
EDGE      3
Edge, bad      296 299
Edge, monochromatic edge      28
Edmonds      8 240 241 249 268
Ehrenfreucht      6
Emden-Weinert      165
Endpoints      3
entropy      133
Erdos      29 34 45 61 82 87 88 285 287 295 296 300
Euler      13
Event      15
Event, independent events      16
Expected value      17
Extension      68
Faber      6
Fajtlowicz      45 244 245
Fellows      61
First Moment Principle      27 36
Fleischner      61
Four Colour Conjecture      9
Fractional chromatic index      239—241 251 267 268
Fractional chromatic number      10 240 266
Fractional colouring      239
Fractional total chromatic index      239
Frieze      82
G-degree      62
Galvin      12
Generalized Tic-Tac-Toe      290—292
Gimbel      34
Godsil      277
Goldberg-Seymour Conjecture      8 10 265
Graph      3
Graph, bipartite      5
Graph, line      4
Graph, perfect      8
Graph, regular      10
Graph, total      4
Graph, triangle free      270
Graph, triangle-free      29 34 37 83 107 125 242 265 266
Greedy colouring algorithm      12 98 100 180
Grimmett      21
Gruenbaum      225
Hadwiger's conjecture      8 9 44 45 49
Haggkvist      139
Hajoes      44—46
Hakken      9
Haxell      41
Hering      94
Hind      68 69 139 224
hits      68
Holyer      6
Hougardy      165
Hyperedge      28
Hypergraph      28
Hypergraph, 2-colouring      39 43 44 287—293 295 297 299 300 302
Hypergraph, 2-colouring proper      28
Hypergraph, colouring      304
Hypergraph, k-uniform      28 139 308
Hypergraph, linear      139
Independent set      3
Indicator variable      28
Interesting component      252
Janssen      139
Jensen      8
Johansson      83 105 107 125
Kahn      10 105 139 251 265
Karp      5
Kayll      251
Kerne      197 198
Kierstead      6
Kim      105 107 108
Komlos      242
Kostochka      49 53 94 107 169
Kreuter      165
Krivelevich      34
Kucera      46
Lagrange      249
Lawrence      107
Lee      249
Lesniak      34
Linearity of expectation      18—20 23 287 288
List chromatic index      11 152
List chromatic number      11 31 33 34 41 87 89
List colouring conjecture      11 12 68 139
Lovasz      39
Lovasz local lemma      39—42 46 55 57 64 70—75 84 98 109 110 113 133 135 144 151 176 188 191 193 197 204 209 212 221—228 266 291 295 297 299 301 302 305 307 309
Lovasz Local Lemma algorithmic      295—313
Lovasz Local Lemma asymmetric      221—225 227
Lovasz Local Lemma, general      222 226—228 304
Lovasz Local Lemma, lopsided      222 228 229 266 268—270 273 274 282 283

Lovasz Local Lemma, weighted      221—224 226 228 304
LP duality      240
Mader      49 53
Maffray      94
Marginal      248
Markov's inequality      27 36 43 298
Martingale inequality      93 94
Matching      3
Matching compatible      252
Matching consistent      261
Matching polytope      249
Mating map      252
McDiarmid      94 169 172 225 228
McDiarmid's Inequality      169 172 173 179 192 202 203 205
Median      19
Method of Conditional Expectations      287—293 296 300
Minor      8 9 49 50 52 53
Minor-balanced      49
Misses      68
Molloy      69 165 166 168 224 301
Monocolourable pair      174
Multigraph      7
Mutual Independence Principle      41 42
Mutually independent      16 17
n-cube      34
Naive Colouring Procedure      83 107—109 126 128 139—141 157 160 166 169 171—173 175 186 195
Nearly bad pair of matchings      262
Neighbour      6
Neighbour, external      158
Neighbour, internal      158
Neighbourhood      5
Nesetfil      87 88
Notation       85
Notation       292
Notation       288
Notation       5
Notation       158
Notation $d_{xy}$       254
Notation       248
Notation $G_{n,p}$       16
Notation $K_{n,n}$       12
Notation $L^{(a,b)}(H)$       197
Notation       6
Notation       269
Notation       17
Notation       253
Notation       241
Notation $Y_{uw}$       177
Notation $Z_{uw}$       177
Notation $\beta$ -figural      224
Notation $\chi^{*}_{e}(G)$       239
Notation $\chi^{*}_{T}(G)$       239
Notation $\chi^{*}_{v}(G)$       239
Notation $\chi^{l}_{e}(G)$       11
Notation $\chi^{l}_{}(G)$       11
Notation $\chi^{}_{e}(G)$       3
Notation $\chi^{}_{T}(G)$       3
Notation $\chi^{}_{}(G)$       3
Notation $\Delta$       5
Notation $\Delta(G)$       5
Notation $\gamma_p$       252
Notation $\mathcal{R}^m$       241
Notation $\mathrm{Big}_i$       199
Notation $\mathrm{Candidate}_w$       212
Notation $\mathrm{Del}_v$       85
Notation $\mathrm{Oftenused}_i$       199
Notation $\mathrm{Overused}_i$       199
Notation $\mathrm{Reserve}_e$       144
Notation $\mathrm{Swappable}_v$       211
Notation $\mathrm{Temp}_i (\alpha)$       206
Notation $\mathrm{Temp}_i$       206
Notation $\omega(G)$       5
Notation $\Omega_X$       17
Notation $\phi(M_1,M_2)$       252
Notation $\prec$       254
Notation $\theta(M_1,M_2)$       252
Notation (1,2)-tree      297
Notation (2,3)-tree      297
Notation Bad      261
Notation BIN(n,p)      18
Notation col(G)      12
Notation Cons      261
Notation d(v)      5
Notation disc(H)      44
Notation E(G)      3
Notation E(X)      17
Notation Ev(x,y)      255
Notation L(G)      4
Notation Med(x)      19
Notation MP(G)      241
Notation N(v)      6
Notation Od(x,y)      255
Notation PR      15
Notation PR(A,B)      16
Notation R(C)      292
Notation rej(v)      207
Notation T(G)      5
Notation V(G)      3
Notation X(C)      288
Ornery set      197 198 217
Padberg      241
Partition class      160
Partition class, non-adjacent      174
Partition class, strongly non-adjacent      174
Preissmann      94
Probability Distribution, hard-core      265—268 270—272 274 277 278 280
Probability Distribution, hardcore      247—264
Probability space      15
Product space      16
Rabinovich      249
Radhakrishnanz      29
Ramsey theory      34
Random variable      17
Rao      241
Reducer      166
Reduction      167
Reed      10 41 69 165 166 168—170 224 225 301
Reject degree, internal      196
Reject edge      185
Reject graph      185
Retains      84
Robertson      9
Roedl      105
Salavatipour      304
Sample space      15
Scheideler      303 304
Selfridge      285 287 295 296 300
Seymour      9
Shamir      82
Shearer      40 242
Simple Concentration Bound      71 79—83 85 86 91 92 103 130 138 151 232 269 276 281
Sinclair      249
Spencer      44 82
Split minor      49 50 52
Srivinasan      29
Stability number      7
Stable set      3
Stable Set, total      3
Steele      82
Steibitz      61
Stirzaker      21
Straight      34
Strong chromatic index      87
Strong chromatic number      61
Strongly r-colourable      61
Subadditivity of Probabilities      16 36
Subdivision      44
Sudakov      34 41 225
Swapping pair      211
Swapping vertex      211

1 2

О проекте