Topics in Graph Theory  book cover
1st Edition

Topics in Graph Theory

  • Available for pre-order on May 22, 2023. Item will ship after June 12, 2023
ISBN 9780367507879
June 12, 2023 Forthcoming by Chapman & Hall
528 Pages 486 B/W Illustrations

FREE Standard Shipping
USD $99.95

Prices & shipping based on shipping country


Book Description

The interplay between graph theory and a wide variety of models and applications in mathematics, computer science, operations research, and the natural and social sciences continues to grow.

This book is geared toward the more mathematically mature student. The first two chapters provide the basic definitions and theorems of graph theory and the remaining chapters introduce a variety of topics and directions for research.  These topics draw on numerous areas of theoretical and applied mathematics, including combinatorics, probability, linear algebra, group theory, topology, operations research, and computer science. This makes the book appropriate for a first course at the graduate level or as a second course at the undergraduate level.

The authors build upon material previously published in Graph Theory and Its Applications, third edition, by the same authors. That text covers material for both an undergraduate and graduate course, while this book builds on and expands the graduate-level material.

List of Features

  • Extensive exercises and applications.
  • Flexibility: appropriate for either a first course at the graduate level; or an advanced course at the undergraduate level.
  • Opens avenues to a variety of research areas in graph theory.
  • Emphasis on topological and algebraic graph theory

Table of Contents

  1. Foundations
    1. Basic Definitions and Terminology
    2. Walks and Connectivity
    3. Subgraphs
    4. Graph Operations
    5. Directed Graphs
    6. Formal Specifications for Graphs and Digraphs

  2. Isomorphisms and Symmetry
    1. Graph Homomorphisms and Isomorphisms
    2. Automorphisms and Symmetry
    3. Tests for Non-Isomorphism

  3. Trees and Connectivity
    1. Characterizations and Properties of Trees
    2. Cycle, Edge-Cuts, and Spanning Trees
    3. Graphs and Vector Spaces
    4. Vertex- and Edge-Connectivity
    5. Max-Min Duality and Menger’s Theorems
    6. Block Decompositions

  4. Planarity and Kuratowski’s Theorem
    1. Planar Drawings and Some Basic Surfaces
    2. Subdivision and Homeomorphism
    3. Extending Planar Drawings
    4. Kuratowski’s Theorem
    5. Algebraic Tests for Planarity
    6. Planarity Algorithm
    7. Crossing Numbers and Thickness

  5. Drawing Graphs and Maps
    1. The Topology of Low Dimensions
    2. Higher-Order Surfaces
    3. Mathematical Model for Drawing Graphs
    4. Regular Maps on a Sphere
    5. Embeddings on Higher-Order Surfaces
    6. Geometric Drawings of Graphs

  6. Graph Colorings
    1. Vertex-Colorings
    2. Local Recolorings
    3. Map-Colorings
    4. Edge-Colorings
    5. Factorization

  7. Measurement and Mappings
    1. Distance in Graphs
    2. Domination in Graphs
    3. Bandwidth
    4. Intersection Graphs
    5. Linear Graph Mappings
    6. Modeling Network Emulation

  8. Analytic Graph Theory
    1. Ramsey Theory
    2. Extremal Graph Theory
    3. Random Graphs

  9. Graph Colorings and Symmetry
    1. Automorphisms of Simple Graphs
    2. Equivalence Classes of Colorings
    3. Burnside’s Lemma
    4. Cycle-Index Polynomial of a Permutation Group
    5. More Counting, Including Simple Groups
    6. Polya-Burnside Enumeration

  10. Algebraic Specification of Graphs
    1. Cyclic Voltages
    2. Specifying Connected Graphs
    3. Zn-Voltage Graphs and Graph Colorings
    4. General Voltage Graphs
    5. Permutation Voltages
    6. Symmetric Graphs and Parallel Architectures

  11. Nonplanar Layouts
    1. Representing Imbeddings by Rotations
    2. Genus Distribution of a Graph
    3. Voltage-Graph Specification of Graph Layouts
    4. Non-KVL Imbedded Voltage Graphs
    5. The Heawood Map-Coloring Problem

View More



Mark Anderson is a professor of mathematics and computer science at Rollins College. His research interests in graph theory center on the topological or algebraic side.

Jonathan L. Gross is a professor of computer science at Columbia University. His research interests include topology and graph theory.

Jay Yellen is a professor of mathematics at Rollins College. His current areas of research include graph theory, combinatorics, and algorithms.