Introduction to Graph Theory, 2/e

Douglas B. West, University of Illinois, Urbana

Coming April, 2000 by Prentice Hall Engineering/Science/Mathematics

Cloth
ISBN 0-13-014400-2

mailings
on this subject.

Graph Theory-Mathematics

Combinatorics-Mathematics

Graph Theory-Computer Science

For undergraduate or graduate courses in Graph Theory in departments of mathematics or computer science. This text offers a comprehensive and coherent introduction to the fundamental topics of graph theory. It includes basic algorithms and emphasizes the understanding and writing of proofs about graphs. Thought-provoking examples and exercises develop a thorough understanding of the structure of graphs and the techniques used to analyze problems.

NEW—Appendix of Mathematical Background—Appendix A presents background material on logical statements, basic set theory, equivalence relations, and elementary counting.

• Makes review material easily accessible for beginning students (Chapter 1 still discusses central proof techniques).
NEW—Expanded and improved selection of exercises—Exercises have been added, especially easier exercises, and many exercises have been further clarified.
• Enlarged selection of easier exercises provides greater encouragement for beginning students and makes the material useful for a broader range of students.
NEW—Reorganization of material. Some material has been reorganized to provide a smoother development and clearer focus on essential material with optional material clearly designated or removed.
• Aids instructors in designing courses and students in seeing what is important.
NEW—Definitions in bold. Terms being defined are in bold type and most important definitions occur in numbered items.
• Makes definitions easier for students to find.
NEW—Hints for selected exercises—More hints have been added in an appendix.
• Allows students to learn at their own pace; weaker students have more opportunity to be successful; stronger students have more opportunity to be stimulated.
Logical organization—Concepts are introduced as needed, achieving a gradual increase in intellectual difficulty.
• Allows students to find fundamental results in the early sections of chapters and to master elementary concepts in preparation for later applications.
• Provides supplementary reading for good students and flexibility in advanced courses. Over 300 illustrations.
• Allows students to check their understanding of definitions and of steps in proofs.
Approximately 1000 exercises—Ranging from relatively straightforward applications of ideas in the text to subtle problems requiring some ingenuity.
• Helps students to understand the ideas of the course and to improve their presentation of coherent arguments.
Graduation of exercises—Marks easier exercises by (-), harder by (+), and particularly valuable or instinctive exercises by (!).
• Aids instructor in selecting appropriate exercises and students in practicing for tests.

1. Fundamental Concepts.
2. Trees and Distance.
3. Matchings and Factors.
4. Connectivity and Paths.
5. Graph Coloring.
6. Planar Graphs.
7. Edges and Cycles.