Graph Structure & Width

← Back to Domain-Specific Families

Abstractions about graph classes, chromatic invariants, expansion, reconstruction, reductions, ends, treewidth, and topological drawing properties.

12 abstractions in this family — domain-specific abstractions that sit near one another in structural-signature space (k-means over structural-signature embeddings). Each is shown with its short description.

• Chromatic polynomial — A graph polynomial P(G,k) whose value at each nonnegative integer k counts the proper vertex colorings of graph G using k labeled colors.
• Chromatic symmetric function — A symmetric-function graph invariant formed as the weight-generating function of all proper vertex colorings by positive integers.
• Cubic Graph — A graph in which every vertex has degree exactly three, creating a sparse regular class with distinctive matching, coloring, symmetry, and Hamiltonicity theory.
• Dually chordal graph — A graph admitting a maximum-neighborhood ordering, equivalently one whose maximal-clique hypergraph has a join tree with the graph’s vertex set as host.
• End (graph theory) — An equivalence class of one-way infinite paths that remain connected in the same unbounded component after deletion of every finite vertex set.
• Expander graph — A sparse finite graph in which every not-too-large vertex set has a proportionally large boundary, equivalently exhibiting strong combinatorial or spectral expansion.
• Graph reduction — Evaluation of a functional program by rewriting a shared expression graph so lazy subexpressions are computed at most once.
• Hanani–Tutte theorem — A planarity theorem stating that a graph is planar when it has a plane drawing in which every pair of independent edges crosses an even number of times.
• Reconstruction conjecture — The conjecture that every finite simple graph with at least three vertices is determined up to isomorphism by the multiset of its vertex-deleted subgraphs.
• Starlike tree — A tree with exactly one vertex of degree greater than two, equivalently several paths joined at one central vertex.
• Transitive reduction — A smallest-edge directed graph preserving exactly the reachability relation of a given directed graph.
• Treewidth — The minimum, over all tree decompositions of a graph, of the largest bag size minus one, measuring how closely the graph can be organized around tree-like separators.