**Contemporary Mathematics**

Volume: 352;
2004;
208 pp;
Softcover

MSC: Primary 05;

Print ISBN: 978-0-8218-3458-9

Product Code: CONM/352

List Price: $69.00

AMS Member Price: $55.20

MAA Member Price: $62.10

**Electronic ISBN: 978-0-8218-7942-9
Product Code: CONM/352.E**

List Price: $69.00

AMS Member Price: $55.20

MAA Member Price: $62.10

# Graph Colorings

Share this page *Edited by *
*Marek Kubale*

Graph coloring is one of the oldest and best-known problems
of graph theory. As people grew accustomed to applying the tools of
graph theory to the solutions of real-world technological and
organizational problems, new chromatic models emerged as a natural way
of tackling many practical situations. Statistics show that graph
coloring is one of the central issues in the collection of several
hundred classical combinatorial problems.

This book is devoted to problems in graph coloring, which can be
viewed as one area of discrete optimization. Chapters are dedicated to
various models and are largely independent of one another. In each
chapter, the author highlights algorithmic aspects of the presented
models, i.e., the construction of polynomial-time algorithms for graph
coloring.

This is an expanded and updated translation of the prizewinning book
originally published in Polish,

#### Readership

Graduate students and research mathematicians interested in graph theory.

# Table of Contents

## Graph Colorings

- Contents v6 free
- Preface ix10 free
- Chapter 1. Classical Coloring of Graphs 114 free
- Chapter 2. On-line Coloring of Graphs 2134
- 2.1. On-line and off-line coloring 2134
- 2.2. On-line coloring algorithms 2336
- 2.3. Worst case effectiveness of on-line coloring 2437
- 2.4. Expected effectiveness of on-line coloring 2740
- 2.5. Susceptibility of graphs 2841
- 2.6. Coloring of intersection graphs 2942
- 2.7. Applications to resource management 3144

- Chapter 3. Equitable Coloring of Graphs 3548
- Chapter 4. Sum Coloring of Graphs 5568
- Chapter 5. T-Coloring of Graphs 6780
- 5.1. The spans 6780
- 5.2. Sets of forbidden distances 6982
- 5.3. T-colorings of graphs 7083
- 5.4. T-spans and T-chromatic numbers 7184
- 5.5. Homomorphisms and T-graphs 7386
- 5.6. Estimates and exact values 7487
- 5.7. The computational complexity 7588
- 5.8. Approximation algorithms 7689
- 5.9. Applications 7790

- Chapter 6. Rank Coloring of Graphs 7992
- Chapter 7. Harmonious Coloring of Graphs 95108
- Chapter 8. Interval Edge-Coloring of Graphs 105118
- Chapter 9. Circular Coloring of Graphs 123136
- Chapter 10. Path Coloring and Routing in Graphs 139152
- Chapter 11. List Colorings of Graphs 153166
- Chapter 12. Ramsey Colorings of Complete Graphs 163176
- Chapter 13. Placing Guards in Art Galleries by Graph Coloring 177190
- Bibliography 189202
- Index 203216 free
- Authors' addresses 207220