Editing Glossary of graph theory (section)

==H==
{{glossary}}

{{term|H|''H''}}
{{defn|A variable often used to denote a graph, especially when another graph has already been denoted by {{mvar|G}}.}}

{{term|H-coloring|''H''-coloring}}
{{defn|An {{mvar|H}}-coloring of a graph {{mvar|G}} (where {{mvar|H}} is also a graph) is a homomorphism from {{mvar|H}} to {{mvar|G}}.}}

{{term|H-tree|''H''-free}}
{{defn|A graph is {{mvar|H}}-free if it does not have an induced subgraph isomorphic to {{mvar|H}}, that is, if {{mvar|H}} is a forbidden induced subgraph. The {{mvar|H}}-free graphs are the family of all graphs (or, often, all finite graphs) that are {{mvar|H}}-free.<ref>{{citation
 | last1 = Brandstädt
 | first1 = Andreas
 | author1-link = Andreas Brandstädt
 | last2 = Le
 | first2 = Van Bang
 | last3 = Spinrad
 | first3 = Jeremy
 | contribution = Chapter 7: Forbidden Subgraph
 | pages = [https://archive.org/details/graphclassessurv0000bran/page/105 105–121]
 | title = Graph Classes: A Survey
 | publisher = SIAM Monographs on Discrete Mathematics and Applications
 | year = 1999
 | isbn = 978-0-89871-432-6
 | url = https://archive.org/details/graphclassessurv0000bran/page/105
 }}</ref> For instance the [[triangle-free graph]]s are the graphs that do not have a [[triangle graph]] as a subgraph. The property of being {{mvar|H}}-free is always hereditary. A graph is {{mvar|H}}-minor-free if it does not have a minor isomorphic to {{mvar|H}}.}}

{{term|Hadwiger}}
{{defn|no=1|[[Hugo Hadwiger]]}}
{{defn|no=2|The [[Hadwiger number]] of a graph is the order of the largest complete minor of the graph. It is also called the contraction clique number or the homomorphism degree.}}
{{defn|no=3|The [[Hadwiger conjecture (graph theory)|Hadwiger conjecture]] is the conjecture that the Hadwiger number is never less than the chromatic number.}}

{{term|Hamiltonian}}
{{defn|A [[Hamiltonian path]] or Hamiltonian cycle is a simple spanning path or simple spanning cycle: it covers all of the vertices in the graph exactly once. A graph is Hamiltonian if it contains a Hamiltonian cycle, and traceable if it contains a Hamiltonian path.}}

{{term|haven}}
{{defn|A {{mvar|k}}-[[Haven (graph theory)|haven]] is a function that maps every set {{mvar|X}} of fewer than {{mvar|k}} vertices to one of its flaps, often satisfying additional consistency conditions. The order of a haven is the number {{mvar|k}}. Havens can be used to characterize the treewidth of finite graphs and the ends and Hadwiger numbers of infinite graphs.}}

{{term|height}}
{{defn|no=1|The ''height'' of a node in a rooted tree is the number of edges in a longest path, going away from the root (i.e. its nodes have strictly increasing depth), that starts at that node and ends at a leaf.}}
{{defn|no=2|The ''height'' of a rooted tree is the height of its root. That is, the ''height'' of a tree is the number of edges in a longest possible path, going away from the root, that starts at the root and ends at a leaf.}}
{{defn|no=3|The ''height'' of a [[directed acyclic graph]] is the maximum length of a directed path in this graph.}}

{{term|hereditary}}
{{defn|A [[hereditary property]] of graphs is a property that is closed under induced subgraphs: if {{mvar|G}} has a hereditary property, then so must every induced subgraph of {{mvar|G}}. Compare {{gli|monotone}} (closed under all subgraphs) or ''minor-closed'' (closed under minors).}}

{{term|[[hexagon]]}}
{{defn|A simple cycle consisting of exactly six edges and six vertices.}}

{{term|hole}}
{{defn|A hole is an induced cycle of length four or more. An odd hole is a hole of odd length. An anti-hole is an induced subgraph of order four whose complement is a cycle; equivalently, it is a hole in the complement graph. This terminology is mainly used in the context of perfect graphs, which are characterized by the [[strong perfect graph theorem]] as being the graphs with no odd holes or odd anti-holes. The hole-free graphs are the same as the [[chordal graph]]s.}}

{{term|homomorphic equivalence}}
{{defn|Two graphs are [[Graph homomorphism|homomorphically equivalent]] if there exist two homomorphisms, one from each graph to the other graph.}}

{{term|homomorphism}}
{{defn|no=1|A [[graph homomorphism]] is a mapping from the vertex set of one graph to the vertex set of another graph that maps adjacent vertices to adjacent vertices. This type of mapping between graphs is the one that is most commonly used in category-theoretic approaches to graph theory. A proper graph coloring can equivalently be described as a homomorphism to a complete graph.}}
{{defn|no=2|The homomorphism degree of a graph is a synonym for its ''Hadwiger number'', the order of the largest clique minor.}}

{{term|hyperarc}}
{{defn|A directed {{gli|hyperedge}} having a source and target set.}}

{{term|hyperedge}}
{{defn|An {{gli|edge}} in a {{gli|hypergraph}}, having any number of endpoints, in contrast to the requirement that edges of graphs have exactly two endpoints.}}

{{term|hypercube}}
{{defn|A [[hypercube graph]] is a graph formed from the vertices and edges of a geometric [[hypercube]].}}

{{term|hypergraph}}
{{defn|A [[hypergraph]] is a generalization of a graph in which each edge (called a hyperedge in this context) may have more than two endpoints.}}

{{term|hypo-}}
{{defn|This prefix, in combination with a graph property, indicates a graph that does not have the property but such that every subgraph formed by deleting a single vertex does have the property. For instance, a [[hypohamiltonian graph]] is one that does not have a Hamiltonian cycle, but for which every one-vertex deletion produces a Hamiltonian subgraph. Compare {{gli|critical}}, used for graphs which have a property but for which every one-vertex deletion does not.<ref>{{citation
 | last = Mitchem | first = John
 | contribution = Hypo-properties in graphs
 | doi = 10.1007/BFb0060121
 | mr = 0253932
 | pages = 223–230
 | publisher = Springer
 | title = The Many Facets of Graph Theory (Proc. Conf., Western Mich. Univ., Kalamazoo, Mich., 1968)
 | volume = 110
 | year = 1969| series = Lecture Notes in Mathematics
 | isbn = 978-3-540-04629-5
 }}.</ref>}}

{{glossary end}}