# 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

* 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

* 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

* 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