Chordal Bipartite Graphs with High Boxicity

Details Chordal Bipartite Graphs with High Boxicity Chordal Bipartite Graphs with High Boxicity

2009-06-02

arxiv.org/abs/0906.0541v2

Mathematics

Combinatorics

9 pages, 1 figure

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Chordal Bipartite Graphs with High Boxicity does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Chordal Bipartite Graphs with High Boxicity, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Chordal Bipartite Graphs with High Boxicity will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-235672