Boxicity and maximum degree


Autoria(s): Chandran, L Sunil; Francis, Mathew C; Sivadasan, Naveen
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

http://eprints.iisc.ernet.in/26048/1/http___www.sciencedirect.com_science__ob%3DMImg%26_imagekey%3DB6WHT-4PP1YHY-1.pdf

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