Contents

Preface

Graph coloring

History of graph coloring

Models of graph coloring

Preface to the English Edition

Chapter 1. Classical Coloring of Graphs

ADRIAN KOSOWSKI, KRZYSZTOF MANUSZEWSKI

1.1. Basic terms and definitions

1.2. Classical vertex-coloring

1.3. Classical edge-coloring

Chapter 2. On-line Coloring of Graphs

PIOTR BOROWIECKI

2.1. On-line and off-line coloring

2.2. On-line coloring algorithms

2.3. Worst case effectiveness of on-line coloring

2.4. Expected effectiveness of on-line coloring

2.5. Susceptibility of graphs

2.6. Coloring of intersection graphs

2.7. Applications to resource management

Chapter 3. Equitable Coloring of Graphs

HANNA FURMANCZYK

3.1. Equitable vertex-coloring

3.2. Equitable total coloring

Chapter 4. Sum Coloring of Graphs

MICHAL MALAFIEJSKI

4.1. Definition and simple properties

4.2. The complexity of the sum coloring problem

4.3. Generalizations of the sum coloring problem

4.4. Some applications of the sum coloring problem

Chapter 5. T-Coloring of Graphs

ROBERT JANCZEWSKI

5.1. The spans

5.2. Sets of forbidden distances

5.3. T-colorings of graphs

5.4. T-spans and T-chromatic numbers

5.5. Homomorphisms and T-graphs

v

ix

ix

X

xi

xii

1

1

6

16

21

21

23

24

27

28

29

31

35

35

50

55

55

58

63

64

67

67

69

70

71

73