Discrete optimization. Models and methods of graph coloring

The book discusses nine selected models of graph coloring; these are coloring: classic, fair, summary, contrast, harmonic, circular, compact, path, letter. The choice of models was made due to the possibilities of their practical applications in areas such as: task scheduling, fiber optic telecommunications, thin-film technology, mobile telephony, aviation radionavigation and production organization. Particular emphasis was placed on the construction of polynomial coloring algorithms - accurate or approximate. Each chapter of the book was written by another Author and is somewhat autonomous, so it can be read independently of the others. The book is intended for the academic community, primarily for students and PhD students of mathematics and computer science, as well as for people interested in discrete optimization, especially programmers.

Table of Contents

Preface of the scientific editor XI
Bibliography XV

Chapter 1. Classic coloring of graphs 1 (Krzysztof Manuszewski) 2

1.1. Basic concepts and definitions 2
1.1.1. Graph families 4
1.1.2. Analysis of approximate methods 5
1.2. Classic vertex coloring 8
1.2.1. The complexity of the problem and the simplest estimates 8
1.2.2. The most common approximate methods are 10
1.2.3. Well-known benczmarki 18
1.3. Edge coloring 19
1.3.1. The complexity of the problem and the simplest estimates
1.3.2. Typical approximate methods - known results 21
1.3.3. NTL 23 method
Bibliography 24

Chapter 2. Metaheuristics in graph coloring (Dariusz Szyfelbein) 26

2.1. Introduction 27
2.1.1. Conditions for terminating the algorithm 28
2.1.2. National team 28
2.1.3. The cost function 29
2.2. Simulated annealing 30
2.2.1. Generating a new solution 32
2.2.2. Cooling schemes 32
2.3. Taboo search 34
2.3.1. Neighborhood and generation of a new solution 35
2.4. Genetic algorithms 36
2.4.1. Initial population and selection of individuals 38
2.4.2. Recombination operators 39
2.4.3. Hybrid algorithms 44
2.5. Antibacterial algorithms 45
2.6. Summary 49
Bibliography 50

Chapter 3. Coloring in online mode (Piotr Borowiecki) 53

3.1. On-line coloring and coloring with? -Line 54
3.2. Basic on-line coloring algorithms 56
3.2.1. Greedy algorithm First-Fit 56
3.2.2. LST 57 algorithm
3.3. Pessimistic efficiency of on-line coloring algorithms 58
3.3.1. Estimates for any algorithms 59
3.3.2. Efficiency of the LST 60 algorithm
3.3.3. Effectiveness of the First-Fit 61 algorithm
3.4. Expected effectiveness of on-line coloring algorithms 61
3.5. On-line coloring of crop intersection graphs 63
3.6. Applications in resource management 66
3.6.1. Dynamic space allocation 66
3.6.2. Allocation of transmission channels in optical network type WDM 68
Bibliography 69

Chapter 4. Fair Coloring of Graphs (Hanna Furmańczyk) 72

4.1. Fair vertigo coloring 72
4.1.1. Polynomial algorithms 83
4.2. Fair edge coloring 85
4.3. Fair and total coloring 88
Bibliography 91

Chapter 5. Summary coloring of graphs (Michał Małafiejski) 93

5.1. Definitions and basic properties of chromatic sum 93
5.2. The complexity of the chromatic sum problem 98
5.2.1. NP-difficult cases 99
5.2.2. Polynomial optimal and approximate algorithms 101
5.3. Generalization of the chromatic sum problem 106
5.3.1. The problem of summation coloring with costs 106
5.3.2. Multichromatic total 107
5.4. Selected sumychromatic applications 108
Bibliography 109

Chapter 6. Contrasting graph coloring (Robert Janczewski) 112

6.1. Spans 112
6.2. Sets of prohibited distances 115
6.3. Contrasting coloring 118
6.4. T span and chromatic number T 119
6.5. Homomorphisms and T graphs 121
6.6. Estimates and exact values 123
6.7. Computational complexity 125
6.7.1. Chromatic number 125
6.7.2. T span 126
6.7.3. T the edge spread 126
6.8. Algorithms approximate 126
6.8.1. The T LF 126 algorithm
6.8.2. The T SL 127 algorithm
6.8.3. The TATAR 128 algorithm
6.9. Applications 128
Bibliography 129

Chapter 7. Harmonical graph coloring (Marek Kubale) 132

7.1. Introduction 133
7.2. Families of graphs with known harmonic chromatic number 135
7.3. Estimation of the harmonic chromatic number for general graphs 139
7.4. Degressive algorithm 140
7.5. Applications 142
Bibliography 145

Chapter 8. Circular graph coloring (Adam Nadolski) 147

8.1. Circular coloring of vertices 147
8.1.1. Circular chromatic number and its properties 147
8.1.2. Determining? C (G) for some graph classes 150
8.1.3. Circular coloring of loaded graphs 153
8.1.4. Application of circular vertices coloring 154
8.2. Circular edge coloring 155
8.2.1. Circular chromatic index 155
8.2.2. Application of circular edge coloring 156
8.2.3. Basic properties 158
Bibliography 165

Chapter 9. The compact edge coloring (Krzysztof Giaro) 167

9.1. Basic properties of the 168 model
9.2. Short-circuit colored bipartite 174
9.3. The span of compact coloring 179
9.4. Deficit graphs 182
Bibliography 188

Chapter 10. Coloring paths in graphs (Jakub Białogrodzki) 190

10.1. Definition of path coloring 191
10.2. Known results on coloring paths 196
10.2.1. Computational complexity 196
10.2.2. General graphs 196
10.2.3. Roads 198
10.2.4. Cycles 200
10.2.5. Trees 202
10.3. Applications 206
Bibliography 207

Chapter 11. Letter coloring of graphs (Konrad Piwakowski) 209

11.1. Basic definitions and properties 210
11.2. Bipartite and 2-selectable graphs 210
11.2.1. Construction of Hajós 213
11.3. D-eligibility and Brooks theorem 215
11.4. Planar charts 217
11.5. Graphs for which? = ?? 218
11.6. Eligibility
11.7. Letter edge coloring 220
Bibliography 223

Chapter 12. Ramsey coloring of solid graphs (Tomasz Dzido) 225

12.1. Basic designations and declarations 226
12.2. Ramsey's theorem and deeds of Ramsey's numbers 227
12.3. Values and properties of Ramsey's classic numbers 229
12.4. Non-classical Ramsey numbers 236
12.4.1. Ramsey numbers of full graphs with one edge removed 236
12.4.2. General graph Ramsey numbers 238
12.4.3. Ramsey numbers for s-uniform hypergrays 239
12.5. Applications of Ramsey numbers 239
12.5.1. An example of the algebraic use of Ramsey's numbers 240
12.5.2. An example of the geometric use of Ramsey's numbers 241
Bibliography 243

Chapter 13. Planning the location of guards in art galleries by method

graph coloring (Paweł Żyliński) 245

13.1. Introduction 245
13.2. The problem of the art gallery 247
13.3. Galleries of any shape without holes 248
13.4. Orthogonal galleries without holes 252
13.5. Ortogonal galleries with holes 255
13.5.1. Number of guards independent of the number of holes 256

Bibliography 259
Index 260
List of designations 266