The Dilworth number of auto-chordal bipartite graphs

DOI10.1007/S00373-014-1471-8MaRDI QIDQ497341zbMATH OpenOpenAlexFDO

Authors Anne Berry, Andreas Brandstädt, Konrad Engel

Publication date 24 September 2015

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1309.5787

zbMATH Keywords

chordal bipartite graphsmirror graphbipartite complementDilworth number

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Structural characterization of families of graphs (05C75)

Abstract: The mirror (or bipartite complement) mir(B) of a bipartite graph B=(X,Y,E) has the same color classes X and Y as B, and two vertices x in X and y in Y are adjacent in mir(B) if and only if xy is not in E. A bipartite graph is chordal bipartite if none of its induced subgraphs is a chordless cycle with at least six vertices. In this paper, we deal with chordal bipartite graphs whose mirror is chordal bipartite as well; we call these graphs auto-chordal bipartite graphs (ACB graphs for short). We describe the relationship to some known graph classes such as interval and strongly chordal graphs and we present several characterizations of ACB graphs. We show that ACB graphs have unbounded Dilworth number, and we characterize ACB graphs with Dilworth number k.

Recommendations

• Several results on chordal bipartite graphs
• Representation characterizations of chordal bipartite graphs
• Classes of bipartite graphs related to chordal graphs
• A \(k\)-partite generalization of chordal bipartite graphs
• Chordal bipartite, strongly chordal, and strongly chordal bipartite graphs

Cites work

• scientific article; zbMATH DE number 3815693 (Why is no real title available?)
• scientific article; zbMATH DE number 3598234 (Why is no real title available?)
• scientific article; zbMATH DE number 3632548 (Why is no real title available?)
• Dismantlable lattices in the mirror
• Doubly Lexical Orderings of Matrices
• Doubly lexical ordering of dense 0--1 matrices
• Efficient graph representations
• Graph Classes: A Survey
• Perfect Elimination and Chordal Bipartite Graphs
• Split Graphs Having Dilworth Number Two
• Split graphs of Dilworth number 2
• Split permutation graphs
• The Complexity of the Partial Order Dimension Problem
• The Dilworth number of auto-chordal bipartite graphs
• Three Partition Refinement Algorithms

Cited in

(2)

• On efficient domination for some classes of H-free bipartite graphs
• The Dilworth number of auto-chordal bipartite graphs

This page was built for publication: The Dilworth number of auto-chordal bipartite graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q497341)