List of graph theory topics
{{Short description|none}}
This is a list of graph theory topics, by Wikipedia page.
See glossary of graph theory for basic terminology.
Examples and types of graphs
{{columns-list|colwidth=30em|
- 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|Graph coloring}}
{{columns-list|colwidth=30em|
- 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
{{columns-list|colwidth=30em|
- 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|Tree (graph theory)}}
{{columns-list|colwidth=30em|
- 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 =
= Operations =
{{columns-list|colwidth=30em|
- 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
Graphs in logic
Mazes and labyrinths
Algorithms
{{See also|Graph algorithms|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
{{columns-list|colwidth=30em|
- 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
}}