Written for advanced undergraduate and beginning graduate students, the fifth edition of this best-selling book provides a wide range of new examples along with historical discussions of mathematicians, problems, and conjectures. It features new and expanded coverage of such topics as toughness, graph minors, perfect graphs, list colorings, nowhere zero flows, list edge colorings, the road coloring problem, and the rainbow number of a graph. Additional applications, exercises, and examples illustrate the concepts and theorems. A solutions manual is available for qualifying instructors.