Boxicity and maximum degree
Data(s) |
01/03/2008
|
---|---|
Resumo |
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 2D2. We also conjecture that the best upper bound is linear in D. |
Formato |
application/pdf |
Identificador |
Chandran, L Sunil and Francis, Mathew C and Sivadasan, Naveen (2008) Boxicity and maximum degree. In: Journal of Combinatorial Theory - Series B, 98 (2). pp. 443-445. |
Publicador |
Elsevier Science |
Relação |
http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6WHT-4PP1YHY-1&_user=512776&_coverDate=03%2F31%2F2008&_rdoc=1&_fmt=high&_orig=search&_sort=d&_docanchor=&view=c&_searchStrId=1239868402&_rerunOrigin=google&_acct=C000025298&_version=1&_urlVersion=0 http://eprints.iisc.ernet.in/26048/ |
Palavras-Chave | #Computer Science & Automation (Formerly, School of Automation) |
Tipo |
Journal Article PeerReviewed |