Graph Regularity & Width Parameters

← Back to Domain-Specific Families

Abstractions that constrain graphs by forbidden substructures or width — even-hole-free graphs, girth, partial k-trees, and homogeneous graphs whose local isomorphisms extend globally — alongside the Frobenius formula for symmetric-group characters derived from related combinatorial data.

6 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.

• Even-hole-free graph — Graph that contains no induced cycle of even length ≥ 6.
• Frobenius Formula — Recover irreducible character values of a symmetric group from partitions and conjugacy-cycle data by extracting a specified monomial coefficient from a product of a Vandermonde factor and power sums.
• Girth (Graph Theory) — Assign an undirected graph the length of its shortest cycle, using infinity for an acyclic graph, to quantify how far local neighborhoods remain tree-like.
• Homogeneous Graph — A graph whose every isomorphism between finite induced subgraphs extends to an automorphism of the entire graph, making all finite local copies globally interchangeable.
• Multitree — A directed acyclic graph in which every ordered pair of vertices has at most one directed path, equivalently a DAG whose reachability order is diamond-free.
• Partial k-tree — A graph that embeds as a subgraph of a k-tree, equivalently one whose treewidth is at most k.