Handbook of Graph Theory, 2nd Edition

Chapter 5

Colorings and Related Topics

Section 5.1 Graph Coloring

Zsolt Tuza

University of Veszprém, Hungary

Introduction

§5.1 concentrates on the classical concept of chromatic number and on the more recent but closely related concept of choice number, mostly in connection with other important graph invariants. Further developments of graph colorings appear in §5.2.

Various problems, some of which are equivalent to colorings (e.g., 1-factorizations) are dealt with in the other sections of this chapter. The book [JeTo95] is a rich source of additional information, where results are organized around more than 200 open problems. On list coloring and related topics, a comprehensive survey can be found in [Tu97] and its update [KrTuVo99]. The recent ...