Abstract: The boxicity of a graph G is defined as the minimum integer k such that G is an intersection graph of axis-parallel k-dimensional boxes. Chordal bipartite graphs are bipartite graphs that do not contain an induced cycle of length greater than 4. It was conjectured by Otachi, Okamoto and Yamazaki that chordal bipartite graphs have boxicity at most 2. We disprove this conjecture by exhibiting an infinite family of chordal bipartite graphs that have unbounded boxicity.
Recommendations
Cites work
- scientific article; zbMATH DE number 3859178 (Why is no real title available?)
- scientific article; zbMATH DE number 3307331 (Why is no real title available?)
- Boxicity and maximum degree
- Boxicity and treewidth
- Characterizations of strongly chordal graphs
- Classes of bipartite graphs related to chordal graphs
- Computing the boxicity of a graph by covering its complement by cointerval graphs
- Geometric representation of graphs in low dimension using axis parallel boxes
- Graph Classes: A Survey
- Interval representations of planar graphs
- On grid intersection graphs
- Perfect Elimination and Chordal Bipartite Graphs
- Relationships between the class of unit grid intersection graphs and other classes of bipartite graphs
Cited in
(7)- Structural properties of word representable graphs
- Grid intersection graphs and boxicity
- Chronological rectangle digraphs which are two-terminal series-parallel
- On orthogonal ray graphs
- Bounds for the boxicity of Mycielski graphs
- Boxicity of line graphs
- Box and Segment Intersection Graphs with Large Girth and Chromatic Number
This page was built for publication: Chordal bipartite graphs with high boxicity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q659714)
