Editing Graph theory (section)

== Problems ==
=== Enumeration ===
There is a large literature on [[graphical enumeration]]: the problem of counting graphs meeting specified conditions. Some of this work is found in Harary and Palmer (1973).

=== Subgraphs, induced subgraphs, and minors ===
A common problem, called the [[subgraph isomorphism problem]], is finding a fixed graph as a [[Glossary of graph theory#Subgraphs|subgraph]] in a given graph. One reason to be interested in such a question is that many [[graph properties]] are ''hereditary'' for subgraphs, which means that a graph has the property if and only if all subgraphs have it too.
Finding maximal subgraphs of a certain kind is often an [[NP-complete problem]]. For example:
* Finding the largest complete subgraph is called the [[clique problem]] (NP-complete).

One special case of subgraph isomorphism is the [[graph isomorphism problem]]. It asks whether two graphs are isomorphic. It is not known whether this problem is NP-complete, nor whether it can be solved in polynomial time.

A similar problem is finding [[induced subgraph]]s in a given graph. Again, some important graph properties are hereditary with respect to induced subgraphs, which means that a graph has a property if and only if all induced subgraphs also have it. Finding maximal induced subgraphs of a certain kind is also often NP-complete. For example:
* Finding the largest edgeless induced subgraph or [[Independent set (graph theory)|independent set]] is called the [[independent set problem]] (NP-complete).

Still another such problem, the minor containment problem, is to find a fixed graph as a minor of a given graph. A [[Minor (graph theory)|minor]] or subcontraction of a graph is any graph obtained by taking a subgraph and contracting some (or no) edges. Many graph properties are hereditary for minors, which means that a graph has a property if and only if all minors have it too. For example, [[Wagner's theorem|Wagner's Theorem]] states: 
* A graph is [[planar graph|planar]] if it contains as a minor neither the [[complete bipartite graph]] ''K''<sub>3,3</sub> (see the [[Three-cottage problem]]) nor the complete graph ''K''<sub>5</sub>.

A similar problem, the subdivision containment problem, is to find a fixed graph as a [[Subdivision (graph theory)|subdivision]] of a given graph. A [[Subdivision (graph theory)|subdivision]] or [[Homeomorphism (graph theory)|homeomorphism]] of a graph is any graph obtained by subdividing some (or no) edges. Subdivision containment is related to graph properties such as [[Planarity (graph theory)|planarity]]. For example, [[Kuratowski's theorem|Kuratowski's Theorem]] states:
* A graph is [[Planar graph|planar]] if it contains as a subdivision neither the [[complete bipartite graph]] ''K''<sub>3,3</sub> nor the [[complete graph]] ''K''<sub>5</sub>.

Another problem in subdivision containment is the [[Kelmans–Seymour conjecture]]:
* Every [[K-vertex-connected graph|5-vertex-connected]] graph that is not [[Planar graph|planar]] contains a [[Homeomorphism (graph theory)|subdivision]] of the 5-vertex [[complete graph]] ''K''<sub>5</sub>.
Another class of problems has to do with the extent to which various species and generalizations of graphs are determined by their ''point-deleted subgraphs''. For example:
* The [[reconstruction conjecture]]

=== Graph coloring ===
{{main|Graph coloring}}
Many problems and theorems in graph theory have to do with various ways of coloring graphs. Typically, one is interested in coloring a graph so that no two adjacent vertices have the same color, or with other similar restrictions. One may also consider coloring edges (possibly so that no two coincident edges are the same color), or other variations. Among the famous results and conjectures concerning graph coloring are the following:
* [[Four-color theorem]]
* [[Strong perfect graph theorem]]
* [[Erdős–Faber–Lovász conjecture]] 
* [[Total coloring|Total coloring conjecture]], also called [[Mehdi Behzad|Behzad]]'s conjecture (unsolved)
* [[List edge-coloring|List coloring conjecture]] (unsolved)
* [[Hadwiger conjecture (graph theory)]] (unsolved)

=== Subsumption and unification ===
Constraint modeling theories concern families of directed graphs related by a [[partial order]]. In these applications, graphs are ordered by specificity, meaning that more constrained graphs—which are more specific and thus contain a greater amount of information—are subsumed by those that are more general. Operations between graphs include evaluating the direction of a subsumption relationship between two graphs, if any, and computing graph unification. The unification of two argument graphs is defined as the most general graph (or the computation thereof) that is consistent with (i.e. contains all of the information in) the inputs, if such a graph exists; efficient unification algorithms are known.

For constraint frameworks which are strictly [[Principle of Compositionality|compositional]], graph unification is the sufficient satisfiability and combination function. Well-known applications include [[Automatic theorem prover|automatic theorem proving]] and modeling the [[Parsing|elaboration of linguistic structure]].

=== Route problems ===
* [[Hamiltonian path problem]]
* [[Minimum spanning tree]]
* [[Route inspection problem]] (also called the "Chinese postman problem")
* [[Seven bridges of Königsberg]]
* [[Shortest path problem]]
* [[Steiner tree]]
* [[Three-cottage problem]]
* [[Traveling salesman problem]] (NP-hard)

=== Network flow ===
There are numerous problems arising especially from applications that have to do with various notions of [[Flow network|flows in networks]], for example:
* [[Max flow min cut theorem]]

=== Visibility problems ===
* [[Museum guard problem]]

=== Covering problems ===
[[Covering problem]]s in graphs may refer to various [[Set cover problem| set cover problems]] on subsets of vertices/subgraphs.
* [[Dominating set]] problem is the special case of set cover problem where sets are the closed [[Neighbourhood (graph theory)|neighborhoods]].
* [[Vertex cover problem]] is the special case of set cover problem where sets to cover are every edges.
* The original set cover problem, also called hitting set, can be described as a vertex cover in a hypergraph.

=== Decomposition problems ===
Decomposition, defined as partitioning the edge set of a graph (with as many vertices as necessary accompanying the edges of each part of the partition), has a wide variety of questions. Often, the problem is to decompose a graph into subgraphs isomorphic to a fixed graph; for instance, decomposing a complete graph into Hamiltonian cycles. Other problems specify a family of graphs into which a given graph should be decomposed, for instance, a family of cycles, or decomposing a complete graph ''K''<sub>''n''</sub> into {{nobreak|''n'' − 1}} specified trees having, respectively, 1, 2, 3, ..., {{nobreak|''n'' − 1}} edges.

Some specific decomposition problems and similar problems that have been studied include:
* [[Arboricity]], a decomposition into as few forests as possible
* [[Cycle double cover]], a collection of cycles covering each edge exactly twice
* [[Edge coloring]], a decomposition into as few [[matching (graph theory)|matching]]s as possible
* [[Graph factorization]], a decomposition of a [[regular graph]] into regular subgraphs of given degrees

=== Graph classes ===
Many problems involve characterizing the members of various classes of graphs. Some examples of such questions are below:
* [[Graph enumeration|Enumerating]] the members of a class
* Characterizing a class in terms of [[Forbidden graph characterization|forbidden substructure]]s
* Ascertaining relationships among classes (e.g. does one property of graphs imply another)
* Finding efficient [[algorithm]]s to [[Decision problem|decide]] membership in a class
* Finding [[Representation (mathematics)|representation]]s for members of a class