Forbidden substructure for interval digraphs/bigraphs

DOI10.1016/j.disc.2015.10.010zbMath1327.05132MaRDI QIDQ898169

Ashok Kumar Das, Sandip Das, Malay Kr. Sen

Publication date: 8 December 2015

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2015.10.010

zbMATH Keywords

circular-arc graphs; Ferrers dimension; edge-asteroids; associated graphs; ATE; exobicliques; Ferrers bigraphs/digraphs; interior positions; interval bigraphs/digraphs

Mathematics Subject Classification ID

05C20: Directed graphs (digraphs), tournaments

Related Items

On some subclasses of interval catch digraphs, Domination number of an interval catch digraph family and its use for testing uniformity, Graphs and digraphs represented by intervals and circular arcs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Permutation bigraphs and interval containments
• Bigraphs/digraphs of Ferrers dimension 2 and asteroidal triple of edges
• Ferrers dimension and boxicity
• On realizable biorders and the biorder dimension of a relation
• Ferrers digraphs and threshold graphs
• On the Ferrers dimension of a digraph
• Characterization problems for graphs, partially ordered sets, lattices, and families of sets
• An interval digraph in relation to its associated bipartite graph
• Recognizing interval digraphs and interval bigraphs in polynomial time
• Short proofs for interval digraphs
• Threshold graphs and related topics
• List homomorphisms and circular arc graphs
• Representation characterizations of chordal bipartite graphs
• The Complexity of the Partial Order Dimension Problem
• Interval digraphs: An analogue of interval graphs
• Interval bigraphs and circular arc graphs
• The recognition of indifference digraphs and generalized semiorders