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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Brandstädt A.: Classes of bipartite graphs related to chordal graphs. Discrete Appl. Math. 32(1), 51–60 (1991)
Brandstädt A., Bang Le V., Spinrad J.P.: Graph Classes: A Survey. SIAM, Philadelphia (1999)
Chandran L.S., Francis M.C., Sivadasan N.: Geometric representation of graphs in low dimension using axis parallel boxes. Algorithmica 56(2), 129–140 (2010)
Chandran L.S., Francis M.C., Sivadasan N.: Boxicity and maximum degree. J. Combinatorial Theory Ser. B 98(2), 443–445 (2008)
Chandran L.S., Sivadasan N.: Boxicity and treewidth. J. Combinatorial Theory Ser. B 97(5), 733–744 (2007)
Cozzens, M.B.: Higher and multidimensional analogues of interval graphs. PhD thesis, Rutgers University, New Brunswick (1981)
Cozzens M.B., Roberts F.S.: Computing the boxicity of a graph by covering its complement by cointerval graphs. Discrete Appl. Math. 6, 217–228 (1983)
Farber M.: Characterizations of strongly chordal graphs. Discrete Math. 43(2–3), 173–189 (1983)
Golumbic, M.C., Goss, C.F.: Perfect elimination and chordal bipartite graphs. J. Graph Theory 2 155–163 (1978)
Golumbic M.C.: Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York (1980)
Hartman I.B.-A., Newman I., Ziv R.: On grid intersection graphs. Discrete Math. 87(1), 41–52 (1991)
Otachi Y., Okamoto Y., Yamazaki K.: Relationships between the class of unit grid intersection graphs and other classes of bipartite graphs. Discrete Appl. Math. 155, 2383–2390 (2007)
Roberts, F.S.: The boxicity and cubicity of a graph. In: Recent Progresses in Combinatorics, pp. 301–310. Academic Press, New York (1969)
Scheinerman, E.R.: Intersection classes and multiple intersection parameters. PhD thesis, Princeton University, Princeton (1984)
Thomassen C.: Interval representations of planar graphs. J. Combinatorial Theory Ser. B 40, 9–20 (1986)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Chandran, L.S., Francis, M.C. & Mathew, R. Chordal Bipartite Graphs with High Boxicity. Graphs and Combinatorics 27, 353–362 (2011). https://doi.org/10.1007/s00373-011-1017-2
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00373-011-1017-2