Milestones in Graph Theory : A Century of Progress.

Format:

Book

Author/Creator:

Beineke, Lowell W., author.

Toft, Bjarne, author.

Wilson, Robin J., author.

Series:

Spectrum Series

Spectrum Series ; v.108

Language:

English

Subjects (All):

Graph theory--History--20th century.

Graph theory.

Physical Description:

1 online resource (142 pages)

Edition:

1st ed.

Place of Publication:

Providence : American Mathematical Society, [2025]

Summary:

This book gives an engaging overview of the advances in graph theory during the 20th century. The authors, all subject experts, considered hundreds of original papers, picking out key developments and some of the notable milestones in the subject. This carefully researched volume leads the reader from the struggles of the early pioneers, through the rapid expansion of the subject in the 1960s and 1970s, up to the present day, with graph theory now a part of mainstream mathematics. After an opening chapter giving an overview of graph theory and its legacy from the 18th and 19th centuries, the book is organized thematically into seven chapters, each covering the developments made in a specified area. Topics covered in these chapters include map colorings, planarity, Hamiltonian graphs, matchings, extremal graph theory, and complexity. Each chapter is supplemented with copious endnotes, providing additional comments, bibliographic details, and further context. Written as an accessible account of the history of the subject, this book is suitable not only for graph theorists, but also for anyone interested in learning about the history of this fascinating subject. Some basic knowledge of linear algebra and group theory would be helpful, but is certainly not essential.

Contents:

Cover

Title page

Copyright

Contents

Preface

Graph Theory Timeline

Chapter 1. Setting the Scene

1.1. Introduction

1.2. Euler and the Königsberg bridges

1.3. Hamiltonian cycles

1.4. Euler's polyhedron formula

1.5. Trees

1.6. The four-color problem

Further Reading

Notes and References

Chapter 2. Coloring Maps and Graphs

2.1. Coloring maps

2.2. Coloring graphs

2.3. Conclusion

Chapter 3. Graphs on Surfaces

3.1. Graphs in the plane

3.2. Crossing numbers

3.3. Graphs on higher surfaces

3.4. Conclusion

Chapter 4. Graphs, Linear Algebra,and Groups

4.1. Linear algebra

4.2. Graphs and groups

4.3. Conclusion

Chapter 5. Cycles, Factorizations,and Matchings

5.1. Hamiltonian graphs

5.2. Factorizations and matchings

5.3. Conclusion

Chapter 6. Minors, Perfect Graphs,and Extremal Graph Theory

6.1. Graph minors

6.2. Perfect graphs

6.3. Extremal graph theory

6.4. Ramsey theory

6.5. Conclusion

Chapter 7. Graph Enumerationand Probability

7.1. Enumeration

7.2. Probability

7.3. Conclusion

Chapter 8. Graph Algorithmsand Complexity

8.1. Algorithms

8.2. Complexity

8.3. Conclusion

Credits

Index

Back Cover.

Notes:

Includes bibliographical references and index.

Description based on publisher supplied metadata and other sources.

ISBN:

1-4704-8121-9

9781470481216