Chordal Bipartite Graphs with High Boxicity


Autoria(s): Chandran, Sunil L; Francis, Mathew C; Mathew, Rogers
Data(s)

01/05/2011

Resumo

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.

Formato

application/pdf

Identificador

http://eprints.iisc.ernet.in/37687/1/Chordal.pdf

Chandran, Sunil L and Francis, Mathew C and Mathew, Rogers (2011) Chordal Bipartite Graphs with High Boxicity. In: Graphs and Combinatorics, 27 (3). pp. 353-362.

Publicador

Springer

Relação

http://www.springerlink.com/content/e131711lpg61585n/

http://eprints.iisc.ernet.in/37687/

Palavras-Chave #Computer Science & Automation (Formerly, School of Automation)
Tipo

Journal Article

PeerReviewed