New characterizations of proper interval bigraphs

DOI10.1016/J.AKCEJ.2015.06.007MaRDI QIDQ896097zbMATH OpenOpenAlexFDO

Authors Ashok Kumar Das, Ritapa Chakraborty

Publication date 11 December 2015

Published in AKCE International Journal of Graphs and Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://doi.org/10.1016/j.akcej.2015.06.007

zbMATH Keywords

astral triple of edgescircularly compatible 1'sdominating pair of verticesmonotone consecutive arrangementproper interval bigraphzero partitionable

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Structural characterization of families of graphs (05C75)

Review text

An interval bigraph is a bipartite graph that can be obtained by assigning an interval to each vertex in such a way that vertices that do not belong to the same partite set are adjacent if and only if the corresponding intervals intersect. Such a graph is called proper if the intervals can also be chosen in such a way that none of them is completely contained in another. This paper provides three new characterisations of proper interval bigraphs: as bipartite graphs avoiding so-called ``astral triples of edges, in terms of the concept of dominating pairs, and by means of the biadjacency matrix.

Recommendations

• New characterizations of proper interval bigraphs and proper circular arc bigraphs
• scientific article; zbMATH DE number 1990673
• Recognizing interval digraphs and interval bigraphs in polynomial time
• Characterizations for unit interval bigraphs
• A new characterization of proper interval graphs

Cites work

• A new characterization of proper interval graphs
• Algorithmic graph theory and perfect graphs
• An Efficient Test for Circular-Arc Graphs
• Asteroidal Triple-Free Graphs
• Bigraphs/digraphs of Ferrers dimension 2 and asteroidal triple of edges
• Characterization problems for graphs, partially ordered sets, lattices, and families of sets
• Characterizations for unit interval bigraphs
• Circular-arc graphs with clique cover number two
• scientific article; zbMATH DE number 3815694 (Why is no real title available?)
• scientific article; zbMATH DE number 1990673 (Why is no real title available?)
• scientific article; zbMATH DE number 1743762 (Why is no real title available?)
• scientific article; zbMATH DE number 861315 (Why is no real title available?)
• scientific article; zbMATH DE number 3307330 (Why is no real title available?)
• Indifference Digraphs: A Generalization of Indifference Graphs and Semiorders
• Interval bigraphs and circular arc graphs
• Interval digraphs: An analogue of interval graphs
• Matrix characterizations of circular-arc graphs
• Recognizing interval digraphs and interval bigraphs in polynomial time
• Representation of a finite graph by a set of intervals on the real line
• Structure theorems for some circular-arc graphs

Cited in

(11)

• A new characterization of proper interval graphs
• Graphs and digraphs represented by intervals and circular arcs
• Characterizations for unit interval bigraphs
• Bigraph impropriety
• scientific article; zbMATH DE number 1990673 (Why is no real title available?)
• scientific article; zbMATH DE number 1743762 (Why is no real title available?)
• scientific article; zbMATH DE number 927077 (Why is no real title available?)
• Circularly compatible ones, D-circularity, and proper circular-arc bigraphs
• New characterizations of proper interval bigraphs and proper circular arc bigraphs
• Asteroidal-triple-free interval \(k\)-graphs
• Bigraphs/digraphs of Ferrers dimension 2 and asteroidal triple of edges

This page was built for publication: New characterizations of proper interval bigraphs

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