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. The forbidden-cycle definition supports structural recognition through equivalent separator, matrix, hypergraph, and elimination-order descriptions.

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.

Scope of Application

Use the class in graph algorithms and structural graph theory with bipartition and induced-cycle status explicit. 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. The closest near miss sets the boundary: 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.

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. The central allowed squares–forbidden long holes tradeoff is this: The class relaxes ordinary chordality at exactly the cycle forced by many bipartite structures. A second global definition–local certificate tension matters because Enumerating cycles is costly while equivalent orderings can certify membership.

Abstract Reasoning

Use three linked moves: verify the proposed two-part vertex partition; search induced cycles rather than arbitrary cycle descriptions; permit four-cycles but test every even length from six upward. As a collapse test, the case exits when an odd cycle or an induced even cycle of length at least six is exhibited. A fourth check is to use a proved separator or elimination certificate when available. A final check is to 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. No canonical parent prime is currently asserted; broader structural comparisons remain related-prime analogies until separately adjudicated in the DAG. The vertex partition is the necessary genus. Chords eliminate induced cycles under a class-specific threshold.

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