List of graph theory topics

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

See glossary of graph theory for basic terminology.

Examples and types of graphs

• Amalgamation
• Bipartite graph
  • Complete bipartite graph
  • Disperser
  • Expander
  • Extractor
• Bivariegated graph
• Cage (graph theory)
• Cayley graph
• Circle graph
• Clique graph
• Cograph
• Common graph
• Complement of a graph
• Complete graph
• Cubic graph
• Cycle graph
• De Bruijn graph
• Dense graph
• Dipole graph
• Directed acyclic graph
• Directed graph
• Distance regular graph
• Distance-transitive graph
• Edge-transitive graph
• Interval graph
• Interval graph, improper
• Interval graph, proper
• Line graph
• Lollipop graph
• Minor
  • Robertson–Seymour theorem
• Petersen graph
• Planar graph
  • Dual polyhedron
  • Outerplanar graph
• Random graph
• Regular graph
• Scale-free network
• Snark (graph theory)
• Sparse graph
  • Sparse graph code
• Split graph
• String graph
• Strongly regular graph
• Threshold graph
• Total graph
• Tree (graph theory).
  See also: § Trees
• Trellis (graph)
• Turán graph
• Ultrahomogeneous graph
• Vertex-transitive graph
• Visibility graph
  • Museum guard problem
• Wheel graph

Graph coloring

Main article: Graph coloring

• Acyclic coloring
• Chromatic polynomial
• Cocoloring
• Complete coloring
• Edge coloring
• Exact coloring
• Four color theorem
• Fractional coloring
• Goldberg–Seymour conjecture
• Graph coloring game
• Graph two-coloring
• Harmonious coloring
• Incidence 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 path
  • Hamiltonian path problem
  • Knight's tour
• Traveling salesman problem
  • Nearest neighbour algorithm
  • Bottleneck traveling salesman problem
• Path analysis (paths and cycles)

Trees

Main article: Tree (graph theory)

• Abstract syntax tree
• B-tree
• Binary tree
  • Binary search tree
    • Self-balancing binary search tree
      • AVL tree
      • Red–black tree
      • Splay tree
      • T-tree
  • Binary space partitioning
  • Full binary tree
• B*-tree
• Heap
  • Binary heap
  • Binomial heap
  • Fibonacci heap
  • 2-3 heap
• Kd-tree
• Cover tree
• Decision tree
• Empty tree
• Evolutionary tree
• Exponential tree
• Family tree
• Fault tree
• Free tree
• Game tree
• K-ary tree
• Octree
• Parse tree
• Phylogenetic tree
• Polytree
• Positional tree
• PQ tree
• R-tree
• Rooted tree
  • Ordered tree
  • Recursive 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 (graph theory)

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

• Tree structure
• Tree data structure
• Cayley's formula
• Kőnig's lemma
• Tree (set theory) (need not be a tree in the graph-theory sense, because there may not be a unique path between two vertices)
• Tree (descriptive set theory)
• Euler tour technique

Graph limits

• Graphon

Graphs in logic

• Conceptual graph
• Entitative graph
• Existential graph
• Laws of Form
• Logical graph

Mazes and labyrinths

• Labyrinth
• Maze
• Maze generation algorithm

Algorithms

See also: Graph algorithms and Algorithm

• Ant colony algorithm
• Breadth-first search
• Depth-first search
• Depth-limited search
• FKT algorithm
• Flood fill
• Graph exploration algorithm
• Matching (graph theory)
• Max flow min cut theorem
• Maximum-cardinality search
• Shortest path
  • Dijkstra's algorithm
  • Bellman–Ford algorithm
  • A* algorithm
  • Floyd–Warshall algorithm
• Topological sorting
  • Pre-topological order

Other topics

• Adjacency list
• Adjacency matrix
  • Adjacency algebra – the algebra of polynomials in the adjacency matrix
• Canadian traveller problem
• Cliques and independent sets
  • Clique problem
• Connected component
• Cycle space
• de Bruijn sequences
• Degree diameter problem
• Entanglement (graph measure)
• Erdős–Gyárfás conjecture
• Eternal dominating set
• Extremal graph theory
  • Critical graph
  • Turán's theorem
• Frequency partition
• Frucht's theorem
• Girth
• Graph drawing
• Graph homomorphism
• Graph labeling
  • Graceful labeling
• Graph partition
• Graph pebbling
• Graph property
• Graph reduction
• Graph-structured stack
• Graphical model
  • Bayesian network
  • D-separation
  • Markov random field
• Tree decomposition (Junction tree) and treewidth
• Graph triangulation (see also Chordal graph)
• Perfect order
• Hidden Markov model
  • Baum–Welch algorithm
  • Viterbi algorithm
• Incidence matrix
• Independent set problem
• Knowledge representation
  • Conceptual graph
  • Mind map
• Level structure
• Link popularity
• Mac Lane's planarity criterion
• Node influence metric
• Reconstruction conjecture
• Scientific classification
  • Cladistics
  • Neighbor-joining
  • Phenetics
• Turán number
• Shannon switching game
• Spectral graph theory
• Spring-based algorithm
• Strongly connected component
• Vertex cover problem

Networks, network theory

See list of network theory topics

Hypergraphs

• Helly family
• Intersection (Line) Graphs of hypergraphs