Even-hole-free graph¶

Graph that contains no induced cycle of even length ≥ 6.

Version: v1 · 2026-09-28 · History
Domain-specific #: 9329
Domain group: Formal Sciences
Origin domain: Mathematics
Subdomains: Graph Theory, Structural Graph Theory → Mathematics

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. A statement about the class must therefore declare its convention.

The restriction concerns induced structure, not the mere presence of even cycles. A graph may contain a long even cycle whose vertex set also contains a chord; that cycle is not a hole, though a smaller induced cycle may still remain. Excluding even holes produces decomposition and neighborhood properties that support structural proofs and algorithms. Recognition asks whether any forbidden induced cycle exists, and polynomial-time algorithms are known despite the global nature of the condition. Optimization problems behave differently within the class: some exploit its structure efficiently, while the complexity of others remains unresolved or convention-dependent. Bisimplicial vertices—vertices whose neighborhoods split into two cliques—are one important structural feature in closely related formulations.

An even-hole-free graph is not necessarily bipartite, chordal, perfect, or free of all even cycles. Odd holes may occur, and a chorded even cycle is allowed. It is also not interchangeable with an even-cycle-free graph unless four-cycles are explicitly forbidden. The abstraction is hereditary avoidance of a particular induced parity pattern: every vertex-induced view of the graph must avoid a chordless even ring of the specified lengths.

Structural Signature¶

Sig role-phrases:

the host graph — vertex-and-edge structure examined through all induced subgraphs
the candidate vertex set — selected vertices retaining every edge present between them in the host
the cycle ring — closed sequence of distinct vertices with consecutive adjacency
the chordlessness condition — absence of edges joining nonconsecutive cycle vertices
the even parity condition — prohibited cycle length belonging to the declared even range
the convention switch — four-cycles either forbidden with all longer even holes or expressly permitted while lengths six and above are excluded
the hereditary avoidance rule — every induced view required to remain free of the specified pattern
the chorded-cycle allowance — even cycles permitted when extra edges prevent them from being holes
the structural consequences — decomposition, neighborhood, and bisimplicial properties enabling proofs and algorithms
the class-boundary distinctions — odd holes, bipartiteness, chordality, perfection, and even-cycle freedom not inferred without additional conditions

What It Is Not¶

Not a graph with no even cycles at all. An even cycle containing a chord is not an even hole.
Not necessarily chordal. Odd chordless cycles can remain.
Not necessarily bipartite. Odd cycles are not excluded by even-hole avoidance.
Not necessarily perfect. Additional forbidden induced structures are needed for that conclusion.
Not convention-independent about four-cycles. Some literature forbids induced C4, while other formulations permit it and exclude only lengths at least six.
Not interchangeable with “even-cycle-free” unless terminology is declared. That stricter phrase can prohibit C4 as well as chorded even cycles depending on context.
Not a property checked on one exhibited drawing. Every vertex-induced subgraph must avoid a chordless cycle of the specified even lengths.

Scope of Application¶

Even-hole-free graph is a graph-theoretic instrument and applies to structural and algorithmic questions about graphs excluding induced chordless cycles of a declared even-length range.

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.
Class comparison. Chordal, perfect, bipartite, even-cycle-free, and odd-hole restrictions are separated.
Induced-cycle methods. Chorded even cycles are distinguished from holes and may conceal smaller forbidden subgraphs.
Applicability boundary. The literature differs on whether C4 is forbidden or only even holes of length at least six, so graph simplicity, finiteness, hole length, induced convention, input model, target problem, and terminology must be declared before results transfer; absence of even holes does not imply absence of all even cycles, odd holes, or perfection.

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. The sharper graph-theoretic question is whether any vertex subset induces a prohibited even cycle exactly, and which decomposition or algorithmic property follows under the chosen class rather than under the stricter even-cycle-free interpretation.

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. This compression is strong enough to yield recurring structural consequences but precise enough that chords matter: an apparent even cycle may be harmless because its induced vertex set contains an additional edge that destroys the hole.

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.

Examples¶

Canonical¶

A graph contains a six-vertex cycle with no edges between nonconsecutive cycle vertices. The selected induced subgraph is therefore a chordless even cycle, so it is an even hole under either common convention and the host is not even-hole-free. If a chord is added, the same six cycle edges still exist but the induced subgraph is no longer a hole. A four-cycle distinguishes conventions: some definitions forbid it, while others permit it and exclude only even holes of length at least six.

Mapped back: Whole graph is the host graph, six vertices the candidate vertex set, cycle the cycle ring, absent diagonals the chordlessness condition, and length six the even parity condition. Four-cycle treatment is the convention switch, while added chord demonstrates the chorded-cycle allowance.

Applied / In Practice¶

An algorithm searches every relevant induced configuration using structural decomposition rather than merely testing whether the graph contains any even cycle. Its documentation fixes the four-cycle convention and validates hereditary closure on induced subgraphs. Results do not imply bipartiteness, chordality, perfection, or absence of odd holes unless separately proved. Bisimplicial and neighborhood properties are used only under the exact class theorem.

Mapped back: Induced closure is the hereditary avoidance rule, algorithms use the structural consequences, and nonimplications enforce the class-boundary distinctions.

Structural Tensions¶

T1 — Identity versus admissible variation. Even-hole-free graph must remain recognizable across legitimate variants. Admissible variation is bounded by this condition: The input is tested for any forbidden induced even cycle under an explicit convention. The stable element is expressed by this invariant: Graph that contains no induced cycle of even length ≥ 6. Treating every surface change as a new abstraction fragments the identity, while allowing a change to the constitutive relation produces a false positive.

Diagnostic: After the proposed variation, can an analyst still establish this invariant: Graph that contains no induced cycle of even length ≥ 6?

T2 — Recognition versus proxy. The domain needs observable or inferential evidence for Even-hole-free graph, but the evidence is not automatically the identity. The working recognition rule is: the class-boundary distinctions — odd holes, bipartiteness, chordality, perfection, and even-cycle freedom not inferred without additional conditions. A familiar indicator can occur without the defining relation, and the relation can persist when a customary detector is unavailable.

Diagnostic: Does the evidence establish the defining claim—Graph that contains no induced cycle of even length ≥ 6—or only a correlated sign?

T3 — Definition versus operational judgment. A compact definition aids reuse, whereas actual classification in mathematics logic statistics can require expert decisions about boundary conditions, measurements, conventions, or exceptions. The restriction concerns induced structure, not the mere presence of even cycles. The definition must constrain those judgments without pretending that every admissible case can be recognized from a label alone.

Diagnostic: Which observation would make a competent practitioner reject the classification under the stated definition?

T4 — Scope versus overextension. Even-hole-free graph has a genuine habitat in which the input is tested for any forbidden induced even cycle under an explicit convention. Yet The literature differs on whether C4 is forbidden or only even holes of length at least six, so graph simplicity, finiteness, hole length, induced convention, input model, target problem, and terminology must be declared before results transfer; absence of even holes does not imply absence of all even cycles, odd holes, or perfection. A useful application map therefore has to be broad enough to cover recurring practice and narrow enough to exclude merely topical or metaphorical occurrences.

Diagnostic: Can the claimed application fill the same carrier and relation roles, or has only the name traveled?

T5 — Transfer versus domain accent. Knowledge about Even-hole-free graph can travel within its home domain, and some structural lessons may travel farther. 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. What transfers must be separated from the specialist vocabulary, warrant, and closure conditions that remain anchored in mathematics logic statistics.

Diagnostic: Is the receiving case a literal instance of Even-hole-free graph, a co-instance of Pattern, or only an analogy?

T6 — Autonomous identity versus forced placement. Even-hole-free graph has a stable source-domain identity—Graph that contains no induced cycle of even length ≥ 6.—but no current live node supplies a necessary genus or structural prerequisite without distortion. Leaving the node unattached preserves the accepted identity and exposes a real gap in the present DAG rather than hiding it under a merely topical parent.

Diagnostic: Would the proposed parent be true of every Even-hole-free graph instance for a reason stronger than shared vocabulary or subject matter?

Structural–Framed Character¶

Even-hole-free graph is structural-leaning, with a bounded disciplinary frame. Its structural side consists of the carrier the host graph — vertex-and-edge structure examined through all induced subgraphs and the constitutive relation Graph that contains no induced cycle of even length ≥ 6. Its framed side comes from mathematics logic statistics, which fixes what the terms denote, what counts as evidence, and when a qualification or exception defeats the classification.

Across the principal tests, the entry is not merely a free-floating pattern. Evaluative weight: the identity can be stated descriptively even when its use has practical or normative consequences. Practice dependence: the class-boundary distinctions — odd holes, bipartiteness, chordality, perfection, and even-cycle freedom not inferred without additional conditions. Institutional stabilization: disciplinary conventions may stabilize the name and test without necessarily creating every underlying event or relation. Vocabulary portability: the invariant is Graph that contains no induced cycle of even length ≥ 6. Import versus recognition: an outside case qualifies literally only if the same typed roles and collapse condition are available; otherwise the comparison is analogical.

No current parent captures the reusable remainder without losing or distorting the defining relation. Even-hole-free graph is therefore admitted as an approved unparented root. This is an explicit graph disposition, not a claim that the abstraction has no relations or that a later densification pass cannot discover one.

Structural Core vs. Domain Accent¶

What is skeletal. The portable skeleton is a typed carrier organized by a constitutive relation, an invariant, a recognition test, and a collapse condition. Here the carrier is the host graph — vertex-and-edge structure examined through all induced subgraphs. The decisive relation is Graph that contains no induced cycle of even length ≥ 6, which also states the controlling invariant at this level. Stripped of specialist nouns, this organization is represented by Pattern.

What is domain-bound. mathematics logic statistics supplies the actual objects or agents, admissible transformations, units or conventions, standards of warrant, and named exceptions. In this case, recognition requires evidence for the class-boundary distinctions — odd holes, bipartiteness, chordality, perfection, and even-cycle freedom not inferred without additional conditions. Admissible variation is bounded by the condition that the input is tested for any forbidden induced even cycle under an explicit convention, and the classification collapses when an even cycle containing a chord is not an even hole. These are constitutive differentia, not illustrative decoration.

Why it remains a domain-specific node. The identity is stable within mathematics_logic_statistics, but no current live parent passes the necessary-relation test. The node is therefore an approved unparented root; future placement must preserve the class-boundary distinctions — odd holes, bipartiteness, chordality, perfection, and even-cycle freedom not inferred without additional conditions rather than attach the name by topical similarity.

This entry is a kind of Network.

Reviewed placement — approved unparented root. No current live node supplies a defensible necessary genus or structural prerequisite for Even-hole-free graph. The reviewed identity is: Graph that contains no induced cycle of even length ≥ 6. Attaching it to the accelerated suggestion would confuse topical similarity with hierarchy; the node is therefore admitted without a parent pending later graph densification.
Nearest catalog surface declined — Triangle-free graph. Its rematch score was 0.317079. Retrieval proximity did not establish synonymy or parentage; the carrier, invariant, and collapse condition remain different.
Related reasoning operations. Evidence, comparison, boundary testing, and representation can support a case without becoming additional DAG parents.

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 (41^st percentile for distinctiveness): it has near-neighbors but no dense thicket of look-alikes.

Family — Graph Regularity & Width Parameters (6 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-08

Not to Be Confused With¶

A forced generic parent. No current live node passed the necessary-relation test. Tell: do not infer hierarchy from shared subject matter, method words, or retrieval proximity; preserve Even-hole-free graph as an approved root until a genuine broader identity is available.
Triangle Free Graph. This is the closest catalog retrieval surface, not an accepted synonym or parent. Tell: Ask which entry's carrier, invariant, and collapse test the case actually satisfies; shared vocabulary or a score of 0.799503 is insufficient.
Not a graph with no even cycles at all. An even cycle containing a chord is not an even hole. Tell: Require the positive recognition condition that the class-boundary distinctions — odd holes, bipartiteness, chordality, perfection, and even-cycle freedom not inferred without additional conditions.
Not necessarily chordal. Odd chordless cycles can remain. Tell: Replace the familiar surface feature and test whether graph that contains no induced cycle of even length ≥ 6.
A detector, representation, or consequence. A method may reveal Even-hole-free graph, a notation may describe it, and an outcome may follow from it without any of those being identical to the abstraction. Tell: Would the defining relation remain if the present detector, notation, or downstream effect changed?
A metaphorical transfer. A case outside the home domain may resemble the structure while lacking its native role types and standards of warrant. Tell: If only the general organization survives, route the comparison to Pattern rather than treating it as another Even-hole-free graph instance.

References¶

Frozen Wikipedia revision: https://en.wikipedia.org/wiki/Even-hole-free_graph (revision 1301019908).
DOI: https://doi.org/10.1016/j.jctb.2007.12.006
DOI: https://doi.org/10.1016/0012-365X(91)90098-M
DOI: https://doi.org/10.1002/jgt.20040
DOI: https://doi.org/10.1002/jgt.10006
DOI: https://doi.org/10.1002/jgt.10045
DOI: https://doi.org/10.1137/1.9781611973099.101
DOI: https://doi.org/10.1016/j.jctb.2015.02.001
DOI: https://doi.org/10.2298/AADM100812027V
Supporting reference preserved in the packet: https://www.graphclasses.org/classes/gc_706.html
Supporting reference preserved in the packet: http://eprints.whiterose.ac.uk/74361/2/decomp-even.pdf
Supporting reference preserved in the packet: http://eprints.whiterose.ac.uk/74360/2/algo-even.pdf
Supporting reference preserved in the packet: http://www.comp.leeds.ac.uk/vuskovi/star.ps
Supporting reference preserved in the packet: http://eprints.whiterose.ac.uk/74347/2/ehfsurvey.pdf
Supporting reference preserved in the packet: https://www.sciencedirect.com/science/article/pii/S0095895623000151
Supporting reference preserved in the packet: http://www.graphclasses.org/classes/gc_547.html
Supporting reference preserved in the packet: http://www.graphclasses.org/index.html

The frozen Wikipedia revision is discovery provenance. The cited source set was reviewed for identity, formal or operational relation, and scope. The encyclopedia's structural synthesis is bounded to those claims; URL transport failure alone was not treated as substantive contradiction.