acyclic orientation, 58

admissible colors, 153

algorithm

LST, 24

connected sequential, 12

Depressive, 101

effective, 24

First-Fit (FF),

23

greedy, 23, 62

greedy independent sets, 14

k-absolute approximation, 4, 61

k-approximation, 62

largest-first (LF), 9, 76

on-line, 21

polynomial time approximation, 61

random sequential, 9

recolor, 18

relative approximation, 4

saturation LF (SLF), 13, 77

Scattered Coloring

(SCC),

30

sequential coloring, 8

SLI, 12

smallest-last (SL), 10, 49, 76

T-DSATUR, 77

T-LF, 76

T-SL, 76

arc expansion, 145

backtracking method, 58

benchmark, 6

Bk,

61

bull, 19

cactus, 4, 76, 110

cartesian product, 108

channel assignment, 32

chromatic sum, 55, 58, 59

Chvatal's Art Gallery Theorem, 177

clique, 2

Cn,

61

cograph, 63, 82

colliding paths, 139

color interchange, 8

color requirement function, 63

Index

203

coloring

best, 55

critical, 165

equitable, 35

greedy, 8

harmonious, 95

k-total, 50

line-distinguishing, 96

of a path, 139

partial harmonious, 100

r-circular, 124, 128

r-fractional, 125

total equitable, 51

vertex, 3

comet, 40, 48, 99

complete network, 163

contiguous multichromatic sum, 64

convex, 173

hull, 173

quadrilateral, 182

quadrilateralization, 182

core of graph, 2

Cr,s,

99

cycle, 3, 76, 98

cyclic production systems, 133

cylinder, 112

D-assignment, 157

~-Equitable

Coloring Conjecture, 38

dart, 64

deficiency, 105

degree of vertex, 1

density, 1

diagonal

internal, 180

digraph

symmetric, 141

dipath, see also path, directed

distance

between vertices, 2

distributed resource allocation, 64

division rule, 164

Dynamic Storage Allocation problem (DSA),

31