Skip to content

Chordal bipartite graph

A bipartite graph in which every cycle of length at least six has a chord, equivalently a bipartite graph with no induced cycle longer than four.

Version
v1 · 2026-09-28 · History
Domain-specific #
8445
Domain group
Formal Sciences
Origin domain
Mathematics
Subdomain
Graph Theory → Mathematics

Core Idea

A chordal bipartite graph is bipartite and has no chordless cycle of length six or more. Equivalently, every such long cycle contains an edge between two nonconsecutive cycle vertices. Induced four-cycles remain legal, which explains why the class is not chordal in the ordinary graph-theoretic sense.

The forbidden-cycle definition supports structural recognition through equivalent separator, matrix, hypergraph, and elimination-order descriptions. Those formulations are useful certificates but must preserve the two-part vertex structure and the exact exemption for four-cycles.

How would you explain it like I'm…

Two-Team Shortcut Loops

Imagine dots split into two teams, red and blue, and lines only connect a red dot to a blue dot. Now look at any big loop you can walk around that uses six or more dots. In a chordal bipartite graph, every big loop like that has a shortcut line across it. Little loops of just four dots are allowed without a shortcut.

Big Loops Need Shortcuts

A graph is dots connected by lines. It's bipartite if the dots split into two groups so every line goes between the groups, never inside one. A chordal bipartite graph is a bipartite graph where every loop of six or more dots has a 'chord', an extra line that cuts across the loop between two dots that aren't next to each other on it. Loops of four are allowed to have no chord, and in fact a four-dot loop in a bipartite graph can't have one. That's why these graphs aren't 'chordal' in the ordinary sense, which requires chords in four-loops too.

Long-Cycle-Chorded Bipartite Graphs

A chordal bipartite graph is a bipartite graph, meaning its vertices split into two sides with edges only between sides, that has no chordless cycle of length six or more. In other words, every cycle with at least six vertices includes a chord, an edge joining two cycle vertices that aren't consecutive on the cycle. Four-cycles are allowed to be chordless; in fact, in a bipartite graph a four-cycle can't have a chord. This means chordal bipartite graphs usually aren't chordal in the ordinary sense, since ordinary chordal graphs forbid chordless cycles longer than three. There are several equivalent ways to recognize these graphs, using separators, matrices, hypergraphs, or special vertex orderings.

 

A chordal bipartite graph is a bipartite graph in which every cycle of length at least six has a chord, an edge between two nonconsecutive vertices of the cycle; equivalently, it has no induced cycle of length six or more. Induced four-cycles remain permitted, and since a bipartite four-cycle cannot contain a chord, the class is generally not chordal in the ordinary sense, where every cycle longer than three must have a chord. The forbidden-cycle definition is equivalent to several structural characterizations, including ones based on separators, matrix representations of the bipartite adjacency, hypergraph properties, and elimination orderings. These serve as certificates for recognition and as tools for algorithms. Any such formulation must preserve the two-sided vertex structure and the precise exemption for four-cycles, or it describes a different class.

Structural Signature

Sig role-phrases:

  • bipartition. Divides vertices into two independent sides. Constitutive graph structure. If altered: An odd cycle violates bipartiteness.
  • long even cycle. Provides a cycle of length at least six to test. Constitutive test object. If altered: Four-cycles are intentionally exempt.
  • nonconsecutive chord. Connects two cycle vertices not adjacent along the cycle. Identity-bearing condition. If altered: A chordless long cycle is a forbidden induced subgraph.
  • induced-subgraph closure. Preserves the exclusion under vertex deletion. Characteristic class property. If altered: Adding outside vertices does not chord an induced cycle.
  • alternative certificate. Uses separators or elimination orderings to recognize the same class. Diagnostic representation. If altered: A certificate must be proved equivalent, not merely correlated.

What It Is Not

  • Chordal graph. Are induced four-cycles forbidden?
  • Weakly chordal graph. Are complements' long holes also excluded?
  • Bipartite graph. Are long induced even cycles unrestricted?
  • Strongly chordal graph. Is an incidence relation rather than class identity being used?

Scope of Application

Use the class in graph algorithms and structural graph theory with bipartition and induced-cycle status explicit.

  • Recognition. Searches for long induced even holes or certificates.
  • Elimination orderings. Provides constructive characterizations.
  • Matrix models. Studies associated binary matrices.
  • Hypergraphs. Connects incidence graphs to strong chordality.
  • Algorithm design. Exploits restricted induced cycles.

Clarity

The word chordal is potentially misleading. The relevant threshold begins at six because bipartite graphs have no odd cycles and may contain chordless squares. Testing only a few cycles or ordinary chordality answers the wrong question.

Manages Complexity

A global forbidden-subgraph condition can be replaced by a local certificate such as an elimination ordering, reducing algorithmic complexity while retaining exact equivalence.

Abstract Reasoning

  1. Verify the proposed two-part vertex partition.
  2. Search induced cycles rather than arbitrary cycle descriptions.
  3. Permit four-cycles but test every even length from six upward.
  4. Use a proved separator or elimination certificate when available.
  5. Produce an explicit odd cycle or long induced hole to refute membership.

Knowledge Transfer

Forbidden-configuration reasoning transfers across hereditary graph classes. The allowed-four-cycle boundary does not: ordinary chordal and weakly chordal classes use different excluded cycles, so their algorithms and theorems require separate checks. The nearest stopping boundary is explicit: A chordal graph is closest: it forbids every induced cycle longer than three, whereas chordal bipartite graphs permit induced four-cycles and forbid longer even holes.

Examples

Canonical

A complete bipartite graph K3,3 contains many six-cycles, but each has nonconsecutive cross edges, so no six-cycle is induced and the graph is chordal bipartite.

Mapped back: bipartition → the two size-three parts; long even cycle → a six-cycle; nonconsecutive chord → additional cross edges; induced-subgraph closure → no induced long hole; alternative certificate → complete separators.

Applied / In Practice

An incidence graph is rejected after six alternating vertices form an induced cycle with no additional incidence edge; one explicit hole is a complete nonmembership certificate.

Mapped back: bipartition → objects and sets; long even cycle → six alternating vertices; nonconsecutive chord → absent; induced-subgraph closure → witness survives as induced subgraph; alternative certificate → forbidden-hole witness.

Structural Tensions

T1: allowed squares vs. forbidden long holes. The class relaxes ordinary chordality at exactly the cycle forced by many bipartite structures. Diagnostic: Is the witness length four or at least six?

T2: global definition vs. local certificate. Enumerating cycles is costly while equivalent orderings can certify membership. Diagnostic: Is the certificate complete?

Structural–Framed Character

Description turns on bipartition, long even cycle, nonconsecutive chord, induced-subgraph closure, alternative certificate. Skeletal core. A two-sorted relation excludes large chordless feedback loops while retaining the minimal rectangle. Domain-bound accent. Vertices, edges, bipartitions, induced cycles, chords, and elimination orderings fix the graph class. Transfer remains bounded because Why not prime. Forbidden-cycle structure transfers, but this is a precise mathematical class. Chordal bipartite graph is structural: vertex partition and induced-cycle constraints are formal and context-independent. Its character: a hereditary bipartite class allowing squares but excluding every longer induced even cycle.

Structural Core vs. Domain Accent

Skeletal core. A two-sorted relation excludes large chordless feedback loops while retaining the minimal rectangle.

Domain-bound accent. Vertices, edges, bipartitions, induced cycles, chords, and elimination orderings fix the graph class.

Why not prime. Forbidden-cycle structure transfers, but this is a precise mathematical class.

  • Bipartite graph. The vertex partition is the necessary genus.
  • Chordality. Chords eliminate induced cycles under a class-specific threshold.
  • No strict parent is asserted because the frozen metadata contains no edge to a verified live bipartite-graph node.

Neighborhood in Abstraction Space

Chordal bipartite graph sits in a sparse region of the domain-specific corpus (66th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Graph Structures & Algorithms (24 abstractions)

Nearest neighbors

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

Not to Be Confused With

  • Chordal graph. Tell: Are induced four-cycles forbidden?
  • Weakly chordal graph. Tell: Are complements' long holes also excluded?
  • Bipartite graph. Tell: Are long induced even cycles unrestricted?
  • Strongly chordal graph. Tell: Is an incidence relation rather than class identity being used?

References

  • Frozen Wikipedia discovery revision: https://en.wikipedia.org/wiki/Chordal_bipartite_graph (revision 1337142435).
  • Preserved source candidate: http://www.graphclasses.org/classes/gc_79.html
  • Preserved source candidate: https://archive.org/details/graphclassessurv0000bran

The frozen Wikipedia revision is discovery provenance. The retained source set was reviewed for identity, formal or operational relation, and scope. The encyclopedia's structural synthesis is bounded to those claims; a thin authority surface is recorded as a nonblocking source-strengthening repair rather than concealed.