Chordal bipartite graphs with high boxicity

DOI10.1007/S00373-011-1017-2zbMATH Open1235.05096arXiv0906.0541OpenAlexW1985734960MaRDI QIDQ659714FDOQ659714

Authors: L. Sunil Chandran, Mathew C. Francis, Rogers Mathew 

Publication date: 24 January 2012

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/0906.0541

Recommendations

• Grid intersection graphs and boxicity
• Upper bound on cubicity in terms of boxicity for graphs of low chromatic number
• Boxicity and poset dimension
• Cubicity, boxicity, and vertex cover
• Boxicity and poset dimension

zbMATH Keywords

interval graphsboxicitychordal bipartite graphsgrid intersection graphs

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Structural characterization of families of graphs (05C75)

Cites Work

• Title not available (Why is that?)
• Graph Classes: A Survey
• Characterizations of strongly chordal graphs
• Interval representations of planar graphs
• Boxicity and treewidth
• Title not available (Why is that?)
• Perfect Elimination and Chordal Bipartite Graphs
• On grid intersection graphs
• Relationships between the class of unit grid intersection graphs and other classes of bipartite graphs
• Classes of bipartite graphs related to chordal graphs
• Boxicity and maximum degree
• Computing the boxicity of a graph by covering its complement by cointerval graphs
• Geometric representation of graphs in low dimension using axis parallel boxes

Cited In (7)

• Bounds for the boxicity of Mycielski graphs
• On orthogonal ray graphs
• Boxicity of line graphs
• Box and Segment Intersection Graphs with Large Girth and Chromatic Number
• Structural properties of word representable graphs
• Grid intersection graphs and boxicity
• Chronological rectangle digraphs which are two-terminal series-parallel

This page was built for publication: Chordal bipartite graphs with high boxicity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q659714)