Editing 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|
* [[Graph amalgamation | Amalgamation]]
* [[Bipartite graph]]
** [[Complete bipartite graph]]
** [[Disperser]]
** [[Expander graph|Expander]]
** [[Extractor (mathematics)|Extractor]]
* [[Bivariegated graph]]
* [[Cage (graph theory)]]
* [[Cayley graph]]
* [[Circle graph]]
* [[Clique graph]]
* [[Cograph]]
* [[Common graph]]
* [[Complement 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]]
* [[Indifference graph|Interval graph, improper]]
* [[Interval graph#Improper interval graphs|Interval graph, proper]]
* [[Line graph]]
* [[Lollipop graph]]
* [[Minor (graph theory)|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 ==<!-- This section is linked from [[Tree (graph theory)]] -->
{{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 (data structure)|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 (mathematics)|Spanning tree]]
**[[Minimum spanning tree]]
***[[Boruvka's algorithm]]
***[[Kruskal's algorithm]]
***[[Prim's algorithm]]
*[[Steiner tree]]
*[[Quadtree]]
}}
=== Terminology ===
*[[Node (graph theory)|Node]]
**[[Child node]]
**[[Parent node]]
**[[Leaf node]]
**[[Root node]]
**[[Root (graph theory)]]
=== 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==

* [[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|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 problem|Shortest path]]
**[[Dijkstra's algorithm]]
**[[Bellman–Ford algorithm]]
**[[A-star algorithm|A* algorithm]]
**[[Floyd–Warshall algorithm]]
*[[Topological sorting]]
**[[Pre-topological order]]

==Other topics==
{{columns-list|colwidth=30em|
*[[Adjacency list]]
*[[Adjacency matrix]]
**[[Adjacency algebra]] &ndash; the algebra of polynomials in the adjacency matrix
*[[Canadian traveller problem]]
*[[Clique (graph theory)|Cliques]] and [[Independent set (graph theory)|independent set]]s
**[[Clique problem]]
*[[Connected component (graph theory)|Connected component]]
*[[Cycle space]]
*[[de Bruijn sequences]]
*[[degree diameter|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 theory)|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]]''

==[[Hypergraph]]s==

*[[Helly family]]
*[[Intersection (Line) Graphs of hypergraphs]]

[[Category:Mathematics-related lists|Graph theory]]
[[Category:Graph theory|*]]
[[Category:Outlines of mathematics and logic|Graph theory]]
[[Category:Outlines|Graph theory]]