Relationships between the class of unit grid intersection graphs and other classes of bipartite graphs

DOI10.1016/J.DAM.2007.07.010MaRDI QIDQ2457021zbMATH OpenOpenAlexFDO

Authors Yota Otachi, Yoshio Okamoto, Koichi Yamazaki

Publication date 29 October 2007

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

Full work available at URL https://doi.org/10.1016/j.dam.2007.07.010

zbMATH Keywords

\(P_{6}\)-free chordal bipartite graphinterval bigraphunit grid intersection graph

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Recommendations

• Characterizations for unit interval bigraphs
• Ferrers dimension of grid intersection graphs
• Simple Geometrical Intersection Graphs
• Mixed unit interval bigraphs
• On grid intersection graphs

Cites work

• A special planar satisfiability problem and a consequence of its NP- completeness
• Chordal bipartite, strongly chordal, and strongly chordal bipartite graphs
• Computing the boxicity of a graph by covering its complement by cointerval graphs
• Doubly Lexical Orderings of Matrices
• Efficient graph representations
• Graph isomorphism completeness for chordal bipartite graphs and strongly chordal graphs
• Grid intersection graphs and boxicity
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 739017 (Why is no real title available?)
• Interval bigraphs and circular arc graphs
• Interval digraphs: An analogue of interval graphs
• On grid intersection graphs
• Permuting matrices to avoid forbidden submatrices
• Recognizing interval digraphs and interval bigraphs in polynomial time
• Representation of a finite graph by a set of intervals on the real line
• Short proofs for interval digraphs
• The neighborhood characteristic parameter for graphs

Cited in

(12)

• Interval bigraphs are unit grid intersection graphs
• Tractabilities and intractabilities on geometric intersection graphs
• Jump number of two-directional orthogonal ray graphs
• Ferrers dimension of grid intersection graphs
• Simple Geometrical Intersection Graphs
• On orthogonal ray graphs
• Proper colorability of segment intersection graphs
• Proper colorability of segment intersection graphs
• Chordal bipartite graphs with high boxicity
• On unit grid intersection graphs and several other intersection graph classes
• Recognition and proper coloring of unit segment intersection graphs
• On orthogonal ray trees

This page was built for publication: Relationships between the class of unit grid intersection graphs and other classes of bipartite graphs

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