Chordal bipartite graph

In the mathematical area of graph theory, a chordal bipartite graph is a bipartite graph B = (X,Y,E) in which every cycle of length at least 6 in B has a chord, i.e., an edge that connects two vertices that are a distance > 1 apart from each other in the cycle. A better name would be weakly chordal and bipartite since chordal bipartite graphs are in general not chordal as the induced cycle of length 4 shows. Chordal bipartite graphs have various characterizations in terms of perfect elimination orderings, hypergraphs and matrices. They are closely related to strongly chordal graphs. By definition, chordal bipartite graphs have a forbidden subgraph characterization as the graphs that do not contain any induced cycle of length 3 or of length at least 5 (so-called holes) as an induced subgraph. Thus, a graph G is chordal bipartite if and only if G is triangle-free and hole-free. In , two other characterizations are mentioned: B is chordal bipartite if and only if every minimal edge separator induces a complete bipartite subgraph in B if and only if every induced subgraph is perfect elimination bipartite. Martin Farber has shown: A graph is strongly chordal if and only if the bipartite incidence graph of its clique hypergraph is chordal bipartite. A similar characterization holds for the closed neighborhood hypergraph: A graph is strongly chordal if and only if the bipartite incidence graph of its closed neighborhood hypergraph is chordal bipartite. Another result found by Elias Dahlhaus is: A bipartite graph B = (X,Y,E) is chordal bipartite if and only if the split graph resulting from making X a clique is strongly chordal. A bipartite graph B = (X,Y,E) is chordal bipartite if and only if every induced subgraph of B has a maximum X-neighborhood ordering and a maximum Y-neighborhood ordering. Various results describe the relationship between chordal bipartite graphs and totally balanced neighborhood hypergraphs of bipartite graphs. A characterization of chordal bipartite graphs in terms of intersection graphs related to hypergraphs is given in.

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Publications associées (31)

Personnes associées (10)

Unités associées (4)

Concepts associés (1)

Cours associés (1)

Séances de cours associées (4)

Graphe cordal

thumb|Un cycle, en noir, avec deux cordes, en vert. Si l'on s'en tient à cette partie, le graphe est cordal. Supprimer l'une des arêtes vertes rendrait le graphe non cordal. En effet, l'autre arête verte formerait, avec les trois arêtes noires, un cycle de longueur 4 sans corde. En théorie des graphes, on dit qu'un graphe est cordal si chacun de ses cycles de quatre sommets ou plus possède une corde, c'est-à-dire une arête reliant deux sommets non adjacents du cycle.

The course aims to introduce the basic concepts and results of modern Graph Theory with special emphasis on those topics and techniques that have proved to be applicable in theoretical computer scienc

Discovering Tonal Profiles with Latent Dirichlet Allocation

Martin Alois Rohrmeier, Fabian Claude Moss

Music analysis, in particular harmonic analysis, is concerned with the way pitches are organized in pieces of music, and a range of empirical applications have been developed, for example, for chord recognition or key finding. Naturally, these approaches r ...

2021

Improved Ramsey-type results for comparability graphs

Istvan Tomon, Dániel József Korándi

Several discrete geometry problems are equivalent to estimating the size of the largest homogeneous sets in graphs that happen to be the union of few comparability graphs. An important observation for such results is that if G is an n-vertex graph that is ...

CAMBRIDGE UNIV PRESS2020

Community-Aware Graph Signal Processing: Modularity Defines New Ways of Processing Graph Signals

Dimitri Nestor Alice Van De Ville, Thomas William Arthur Bolton, Raphaël Pierre Liégeois

The emerging field of graph signal processing (GSP) allows one to transpose classical signal processing operations (e.g., filtering) to signals on graphs. The GSP framework is generally built upon the graph Laplacian, which plays a crucial role in studying ...

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2020

Analyse statistique des données du réseau MATH-448: Statistical analysis of network data

Introduit des structures de données réseau, des modèles et des techniques d'analyse, mettant l'accent sur l'invariance de permutation et les réseaux Erdős-Rényi.

Traitement des données du réseau CS-401: Applied data analysis

Couvre la gestion des données du réseau, les types de graphiques, les mesures de centralité et les propriétés des réseaux du monde réel.

Graphiques bipartites et n-partites

Couvre les graphes bipartites et n-partites, y compris les définitions complètes des graphes et des exemples.