A note on lower bounds for boxicity of graphs
Abstract
The boxicity of a graph G is the minimum non-negative integer k such that G is isomorphic to the intersection graph of a family of boxes in Euclidean k-space, where a box in Euclidean k-space is the Cartesian product of k closed intervals on the real line. In this short note, we define the fractional boxicity of a graph as the optimum value of the linear relaxation of a covering problem with respect to boxicity, which gives a lower bound for its boxicity. We show that the fractional boxicity of a graph is at least the lower bounds for boxicity given by Adiga et al. in 2014. We also present a natural lower bound for fractional boxicity of graphs. The aim of this note is to discuss and focus on “accuracy” rather than “simplicity” of these lower bounds for boxicity as the next step in the work by Adiga et al.
Keywords
Full Text:
PDFDOI: http://dx.doi.org/10.5614/ejgta.2024.12.1.12
References
A. Adiga, D. Bhowmick, and L.S. Chandran, Boxicity and poset dimension, SIAM J. Discrete Math. 25 (2011), 1687–1698.
A. Adiga, L.S. Chandran and N. Sivadasan, Lower bounds for boxicity, Combinatorica 34 (2014), 631–655.
L.S. Chandran, A. Das, and C.D. Shah, Cubicity, boxicity, and vertex cover, Discrete Math. 309 (2009), 2488–2496.
L.S. Chandran, M.C. Francis, and N. Sivadasan, Boxicity and maximum degree, J. Combin. Theory Ser. B 98 (2008), 443–445.
L.S. Chandran and N. Sivadasan, Boxicity and treewidth, J. Combin. Theory Ser. B 97 (2007), 733–744.
M.B. Cozzens, Higher and Multidimensional Analogues of Interval Graphs, Ph.D. Thesis, Rutgers University, New Brunswick, NJ, 1981.
M.B. Cozzens and F.S. Roberts, Computing the boxicity of a graph by covering its complement by cointerval graphs, Discrete Appl. Math. 6 (1983), 217–228.
L. Esperet, Boxicity of graphs with bounded degree, European J. Combin. 30 (2009), 1277–1280.
L. Esperet and G. Joret, Boxicity of graphs on surfaces, Graphs Combin. 29 (2013), 417–427.
L. Esperet, Boxicity and topological invariants, European J. Combin. 51 (2016), 495–499.
L. Esperet, Box representations of embedded graphs, Discrete Comput. Geom. 57 (2017), 590–606.
L. Esperet and V. Wiechert, Boxicity, poset dimension, and excluded minors, Electron. J. Combin. 25 (2018) #P4.51.
M.Fekete, Über die Verteilung der Wurzeln bei gewissen algebraischen Gleichungen mit ganzzahligen Koeffizienten, Math. Zeit. 17 (1923), 228–249.
L.C. Freeman, Spheres, cubes and boxes: Graph dimensionality and network structure, Soc. Netw. 5 (1983), 139–156.
F.S. Roberts, On the boxicity and cubicity of a graph, in: Recent Progress in Combinatorics, Academic Press, New York (1969) 301-310.
F.S. Roberts, Discrete Mathematical Models, with Applications to Social, Biological, and Environmental Problems, Prentice-Hall, New Jersey, 1976.
E.R. Scheinerman, Intersection Classes and Multiple Intersection Parameters, Ph.D. Thesis, Princeton University, 1984.
E. R. Scheinerman and D.H. Ullman, Fractional Graph Theory, A rational Approach to the Theory of Graphs, Dover Publications, Inc. Mineola, New York, 2011.
A. Scott and D.R. Wood, Better bounds for poset dimension and boxicity, Trans. Amer. Math. Soc. 373 (2020), 2157–2172.
C. Thomassen, Interval representations of planar graphs, J. Combin. Theory Ser. B 40 (1986), 9–20.
Refbacks
- There are currently no refbacks.
ISSN: 2338-2287
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.