Hardcover ISBN:  9781470453428 
Product Code:  AMSTEXT/43 
List Price:  $85.00 
MAA Member Price:  $76.50 
AMS Member Price:  $68.00 
Electronic ISBN:  9781470455491 
Product Code:  AMSTEXT/43.E 
List Price:  $85.00 
MAA Member Price:  $76.50 
AMS Member Price:  $68.00 

Book DetailsPure and Applied Undergraduate TextsVolume: 43; 2020; 336 ppMSC: Primary 05;
Graph theory is a fascinating and inviting branch of mathematics. Many problems are easy to state and have natural visual representations, inviting exploration by new students and professional mathematicians. The goal of this textbook is to present the fundamentals of graph theory to a wide range of readers. The book contains many significant recent results in graph theory, presented using uptodate notation. The author included the shortest, most elegant, most intuitive proofs for modern and classic results while frequently presenting them in new ways. Major topics are introduced with practical applications that motivate their development, and which are illustrated with examples that show how to apply major theorems in practice. This includes the process of finding a brute force solution (casechecking) when an elegant solution is not apparent. With over 1200 exercises, internet resources (e.g., the OEIS for counting problems), helpful appendices, and a detailed guide to different course outlines, this book provides a versatile and convenient tool for the needs of instructors at a large variety of institutions.
ReadershipUndergraduate and graduate students interested in graph theory.

Table of Contents

Cover

Preface

Chapter 1. Basics of Graphs

1.1. Graphs as Models

1.2. Representations of Graphs

1.3. Graph Parameters

1.4. Common Graph Classes

1.5. Graph Operations

1.6. Distance

1.7. Bipartite Graphs

1.8. Generalizations of Graphs

Exercises

Chapter 2. Trees and Connectivity

2.1. Trees

2.2. Tree Algorithms

2.3. Connectivity

2.4. Menger’s Theorem

Exercises

Chapter 3. Structure and Degrees

3.1. Eulerian Graphs

3.2. Graph Isomorphism

3.3. Degree Sequences

3.4. Degeneracy

Exercises

Chapter 4. Vertex Coloring

4.1. Applications of Coloring

4.2. Coloring Bounds

4.3. Coloring and Operations

4.4. Extremal 𝑘chromatic Graphs

4.5. Perfect Graphs

Exercises

Chapter 5. Planarity

5.1. The Four Color Theorem

5.2. Planar Graphs

5.3. Kuratowski’s Theorem

5.4. Dual Graphs and Geometry

5.5. Genus of Graphs

Exercises

Chapter 6. Hamiltonian Graphs

6.1. Finding Hamiltonian Cycles

6.2. Hamiltonian Applications

6.3. Hamiltonian Planar Graphs

6.4. Tournaments

Exercises

Chapter 7. Matchings

7.1. Bipartite Matchings

7.2. Tutte’s 1Factor Theorem

7.3. Edge Coloring

7.4. Tait Coloring

7.5. Domination

Exercises

Chapter 8. Generalized Graph Colorings

8.1. List Coloring

8.2. Vertex Arboricity

8.3. Grundy Numbers

8.4. Distance and Sets

Exercises

Chapter 9. Decompositions

9.1. Decomposing Complete Graphs

9.2. General Decompositions

9.3. Ramsey Numbers

9.4. NordhausGaddum Theorems

Exercises

Chapter 10. Appendices

10.1. Proofs

10.2. Counting Techniques and Identities

10.3. Computational Complexity

10.4. Bounds and Extremal Graphs

10.5. Graph Characterizations

Nomenclature

Bibliography

Index

Back Cover


Additional Material

Reviews

...this is an attractive new addition to the upperlevel undergraduate textbook literature on graph theory, and anybody planning to teach such a course should certainly make its acquaintance, as should anyone who wants a good graph theory reference. I'm glad it's on my shelf.
Mark Hunacek, Iowa State University


RequestsReview Copy – for reviewers who would like to review an AMS bookDesk Copy – for instructors who have adopted an AMS textbook for a courseExamination Copy – for faculty considering an AMS textbook for a coursePermission – for use of book, eBook, or Journal contentAccessibility – to request an alternate format of an AMS title
 Book Details
 Table of Contents
 Additional Material
 Reviews
 Requests
Graph theory is a fascinating and inviting branch of mathematics. Many problems are easy to state and have natural visual representations, inviting exploration by new students and professional mathematicians. The goal of this textbook is to present the fundamentals of graph theory to a wide range of readers. The book contains many significant recent results in graph theory, presented using uptodate notation. The author included the shortest, most elegant, most intuitive proofs for modern and classic results while frequently presenting them in new ways. Major topics are introduced with practical applications that motivate their development, and which are illustrated with examples that show how to apply major theorems in practice. This includes the process of finding a brute force solution (casechecking) when an elegant solution is not apparent. With over 1200 exercises, internet resources (e.g., the OEIS for counting problems), helpful appendices, and a detailed guide to different course outlines, this book provides a versatile and convenient tool for the needs of instructors at a large variety of institutions.
Undergraduate and graduate students interested in graph theory.

Cover

Preface

Chapter 1. Basics of Graphs

1.1. Graphs as Models

1.2. Representations of Graphs

1.3. Graph Parameters

1.4. Common Graph Classes

1.5. Graph Operations

1.6. Distance

1.7. Bipartite Graphs

1.8. Generalizations of Graphs

Exercises

Chapter 2. Trees and Connectivity

2.1. Trees

2.2. Tree Algorithms

2.3. Connectivity

2.4. Menger’s Theorem

Exercises

Chapter 3. Structure and Degrees

3.1. Eulerian Graphs

3.2. Graph Isomorphism

3.3. Degree Sequences

3.4. Degeneracy

Exercises

Chapter 4. Vertex Coloring

4.1. Applications of Coloring

4.2. Coloring Bounds

4.3. Coloring and Operations

4.4. Extremal 𝑘chromatic Graphs

4.5. Perfect Graphs

Exercises

Chapter 5. Planarity

5.1. The Four Color Theorem

5.2. Planar Graphs

5.3. Kuratowski’s Theorem

5.4. Dual Graphs and Geometry

5.5. Genus of Graphs

Exercises

Chapter 6. Hamiltonian Graphs

6.1. Finding Hamiltonian Cycles

6.2. Hamiltonian Applications

6.3. Hamiltonian Planar Graphs

6.4. Tournaments

Exercises

Chapter 7. Matchings

7.1. Bipartite Matchings

7.2. Tutte’s 1Factor Theorem

7.3. Edge Coloring

7.4. Tait Coloring

7.5. Domination

Exercises

Chapter 8. Generalized Graph Colorings

8.1. List Coloring

8.2. Vertex Arboricity

8.3. Grundy Numbers

8.4. Distance and Sets

Exercises

Chapter 9. Decompositions

9.1. Decomposing Complete Graphs

9.2. General Decompositions

9.3. Ramsey Numbers

9.4. NordhausGaddum Theorems

Exercises

Chapter 10. Appendices

10.1. Proofs

10.2. Counting Techniques and Identities

10.3. Computational Complexity

10.4. Bounds and Extremal Graphs

10.5. Graph Characterizations

Nomenclature

Bibliography

Index

Back Cover

...this is an attractive new addition to the upperlevel undergraduate textbook literature on graph theory, and anybody planning to teach such a course should certainly make its acquaintance, as should anyone who wants a good graph theory reference. I'm glad it's on my shelf.
Mark Hunacek, Iowa State University