Width of a tree decomposition of an undirected graph, one less than the size of the largest vertex-set in the decomposition.
Width of a path decomposition of an undirected graph, one less than the size of the largest set in the decomposition
Width of a branch decomposition of an undirected graph, the maximum number of shared vertices of any pair of subgraphs formed by removing an edge from the tree.
Clique-width of a graph, the minimum number of distinct labels needed to construct G by operations that create a labeled vertex, form the disjoint union of two labeled graphs, add an edge connecting all pairs of vertices with given labels, or relabel all vertices with a given label.
The width of a graph is an alternative name for the degeneracy of the graph - the smallest k for which every subgraph has a vertex of degree at most k.
Bandwidth of a graph - the minimum, over all orderings of vertices of G, of the length of the longest edge (the number of steps in the ordering between its two endpoints).
Width of a hypergraph - the size of a smallest subset of edges that meets all other edges.
This disambiguation page lists articles associated with the title Width. If an internal link led you here, you may wish to change the link to point directly to the intended article.
