1. Boxicity and maximum degree
- Author
-
Sunil Chandran, L., Francis, Mathew C., and Sivadasan, Naveen
- Subjects
- *
INTERSECTION graph theory , *BOXES , *MATHEMATICS , *COMPLETE graphs - Abstract
Abstract: A d-dimensional box is a Cartesian product of d closed intervals on the real line. The boxicity of a graph is the minimum dimension d such that it is representable as the intersection graph of d-dimensional boxes. We give a short constructive proof that every graph with maximum degree D has boxicity at most . We also conjecture that the best upper bound is linear in D. [Copyright &y& Elsevier]
- Published
- 2008
- Full Text
- View/download PDF