Even-hole-free graph¶
Graph that contains no induced cycle of even length ≥ 6.
Core Idea¶
An even-hole-free graph is a graph whose induced subgraphs contain no chordless cycle of even length in the prohibited range. A hole is an induced cycle, ordinarily of length at least four: among the vertices on the cycle, the graph has exactly the cycle edges and no chord joining nonconsecutive vertices. Under one convention, even holes of every even length at least four are forbidden. Under another used in parts of the literature, four-cycles are permitted and only induced even cycles of length at least six are excluded; the stricter class is then called even-cycle-free.
Scope of Application¶
-
Recognition algorithms. The input is tested for any forbidden induced even cycle under an explicit convention.
-
Hereditary-class theory. Every induced subgraph inherits the avoidance property.
-
Decomposition theorems. Structural pieces and separators exploit restrictions created by missing even holes.
-
Neighborhood analysis. Bisimplicial and related vertex properties support proofs and algorithms in appropriate formulations.
-
Optimization problems. Complexity and algorithms are studied within the exact class rather than inferred from recognition alone.
Clarity¶
Even-hole-free graph forbids induced chordless cycles of specified even lengths, not every even cycle. A cycle with a chord is not a hole, and literature conventions differ on whether a four-cycle counts among the forbidden holes or only lengths six and above are excluded. Naming that convention is essential.
Manages Complexity¶
Even-hole-free classification compresses a graph's many cycles to one induced-subgraph exclusion. The analyst tracks chordless even cycles and the convention about four-cycles rather than forbidding every even closed walk. Decomposition theorems can then route the graph through simpler structural pieces, and recognition or optimization algorithms exploit the absent configuration. Strict and length-at-least-six branches must remain separate.
Abstract Reasoning¶
Recognition move. Search a graph for induced cycles of even length at least four and certify membership only when none exists. Chord move. Distinguish a hole from an ordinary cycle by checking that nonconsecutive vertices have no connecting edges. Structural move. Use decompositions and forbidden configurations developed for the class to reason about coloring, optimization, or recognition. Hereditary move. Infer that induced subgraphs remain even-hole-free. Boundary move. Even-hole-free does not mean cycle-free, bipartite, chordal, or free of odd holes; even cycles with chords do not violate the definition.
Knowledge Transfer¶
Within the home domain. Even-hole-free graphs transfer across structural graph theory, recognition algorithms, coloring, and optimization as graphs containing no induced even cycle of length at least four. Vertex, edge, chord, induced subgraph, hole parity, and hereditary structure retain exact roles. Beyond the home domain (C — graph class). Any modeled network can be tested literally, but class membership concerns its graph representation rather than the source domain's mechanism. Its boundary is precise: even cycles with chords are allowed, odd holes may occur, and the class is neither chordal, bipartite, cycle-free, nor defined by geometric holes.
Relationships to Other Abstractions¶
Current abstraction Even-hole-free graph Domain-specific
Parents (1) — more general patterns this builds on
-
Even-hole-free graph is a kind of Network Prime
Even-hole-free graph is a domain-specific kind of graph under its frozen identity and differentia. Complete-catalog comparison found the corresponding live broader identity.
Hierarchy path (1) — routes to 1 parentless root
- Even-hole-free graph → Network → Reservoir-Flux Network → Conservation Laws → Invariance
Neighborhood in Abstraction Space¶
Even-hole-free graph sits in a moderately populated region (41st percentile for distinctiveness): it has near-neighbors but no dense thicket of look-alikes.
Family — Graph Regularity & Width Parameters (6 abstractions)
Nearest neighbors
- Tree (Graph Theory) — 0.89
- Polygon — 0.88
- Chordal bipartite graph — 0.87
- Connected Dominating Set — 0.87
- Biconnected Component — 0.86
Computed from structural-signature embeddings · 2026-10-08