List of graph theory topics - Definition and Overview

This is a list of graph theory topics, by Wikipedia page.

See glossary of graph theory for basic terminology

Examples and types of graphs

See also Trees

• Bipartite graph
  • Complete bipartite graph
  • Disperser
  • Expander
  • Extractor
• Cayley graph
• Complete graph
• Directed acyclic graph
• Interval graph
• Inverse graph
• Line graph
• Petersen graph
• Planar graph
  • Dual polyhedron
  • Outerplanar graph
• Regular graph
• Turán graph
• Edge-transitive graph
• Vertex-transitive graph

Graph coloring

• Acyclic coloring
• Chromatic polynomial
• Cocoloring
• Complete coloring
• Edge coloring
• Exact coloring
• Four color theorem
• Fractional coloring
• Harmonious coloring
• List coloring
• List edge-coloring
• Perfect graph
• Ramsey's theorem
• Sperner's lemma
• Strong coloring
• Subcoloring
• Tait's conjecture
• Total coloring
• Uniquely colorable graph

Paths and cycles

• Path (graph theory)
• Seven bridges of Königsberg
  • Eulerian path
• Three cottage problem
• Shortest path problem
  • Dijkstra's algorithm
    • Open shortest path first
• Flooding algorithm
• Route inspection problem
• Hamiltonian cycle problem, Hamiltonian path
  • Knight's Tour
    • How to solve the knight's tour
• Traveling salesman problem
  • Nearest neighbour algorithm
  • Bottleneck traveling salesman problem
• Path analysis

Trees

• Tree
  • Abstract syntax tree
  • B-tree
    • 2-3 tree
  • Binary tree
    • Binary search tree
      • Self-balancing binary search tree
        • AVL tree
        • Red-black tree
        • Splay tree
    • Binary space partitioning
    • Full binary tree
  • B*-tree
  • Heap
    • Binary heap
    • Binomial heap
    • Fibonacci heap
    • 2-3 heap
  • Charles' tree
  • Decision tree
  • Empty tree
  • Evolutionary tree
  • Exponential tree
  • Family tree
  • Fault tree
  • Free tree
  • Game tree
  • Infinite tree
  • K-ary tree
  • Octree
  • Parse tree
  • Phylogenetic tree
  • Positional tree
  • PQ tree
  • R-tree
  • Rooted tree
    • Ordered tree
  • SPQR tree
  • Suffix tree
  • Technology tree
  • Trie
    • Patricia trie
  • Spanning tree
    • Minimum spanning tree
      • Boruvka's algorithm
      • Kruskal's algorithm
      • Prim's algorithm
  • Steiner tree
  • Quadtree
• Terminology
  • Node
    • Child node
    • Parent node
    • Leaf node
    • Root node
    • Root (computing)
• Operations
  • Tree rotation
  • Tree traversal
    • Inorder traversal
    • Backward inorder traversal
    • Pre-order traversal
    • Post-order traversal
    • Ahnentafel
  • Tree search algorithm
  • A-star search algorithm
  • Best-first search
  • Breadth-first search
  • Depth-first search
    • Iterative deepening depth-first search
• Other
  • Tree structure
  • Tree data structure
  • Cayley's formula
  • König's lemma
  • MUD trees

Mazes

• Maze generation algorithm
• Labyrinth

Algorithms

• Flood fill
• Graph exploration algorithm
• Ant colony algorithm
• Max flow min cut theorem
• Breadth-first search
• Depth-first search
• Depth-limited search
• Shortest path
  • Dijkstra's algorithm
  • Bellman-Ford algorithm
  • A* algorithm
  • Floyd-Warshall algorithm
• Topological sorting

Other topics

• Graph property
• Graph drawing
• Adjacency matrix
  • Link popularity
• Adjacency list
• Incidence matrix
• Graph homomorphism
• Clique problem, clique, independent set
• Girth
• Cycle space
• Minor (graph theory)
  • Robertson-Seymour theorem
• Extremal graph theory
  • Critical graph
  • Turán's theorem
• Spectral graph theory
• Random graph
• Erdös-Gyárfás conjecture
• Shannon switching game
• Spring based algorithm
• Directed graph
  • Strongly connected component
• Scientific classification
  • Cladistics
  • Neighbor-joining
  • Phenetics
• Knowledge representation
  • Conceptual graph
  • Mind map
• Graphical model
• Graph reduction
• Sparse graph code
• Vertex cover problem
• Graph-structured stack
• Level structure
• MacLane's planarity criterion
• Sparse graph
• Cubic graph
• Snark (graph theory)
• Independent set problem
• Reconstruction set problem
• Visibility graph, museum guard problem

Networks, network theory

See list of network theory topics

Hypergraphs

• Helly family