Boxicity and maximum degree

DOI10.1016/J.JCTB.2007.08.002MaRDI QIDQ2477634zbMATH OpenOpenAlexFDO

Authors L. Sunil Chandran, Mathew C. Francis, Naveen Sivadasan

Publication date 14 March 2008

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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

zbMATH Keywords

boxicitychromatic numbermaximum degreesquare of a graph

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62)

Abstract: An axis-parallel $d$--dimensional box is a Cartesian product $R_{1}imes{R}_{2}imes\mathrm{...}imes{R}_d$ where $R_i$ (for $1leiled$) is a closed interval of the form $[a_i,b_i]$ on the real line. For a graph $G$, its emph{boxicity} $$ is the minimum dimension $d$, such that $G$ is representable as the intersection graph of (axis--parallel) boxes in $d$--dimensional space. The concept of boxicity finds applications in various areas such as ecology, operation research etc. We show that for any graph $G$ with maximum degree $Delta$, $$. That the bound does not depend on the number of vertices is a bit surprising considering the fact that there are highly connected bounded degree graphs such as expander graphs. Our proof is very short and constructive. We conjecture that $$ is $O(Delta)$.

Recommendations

• Boxicity of graphs with bounded degree
• Geometric Representation of Graphs in Low Dimension
• Geometric representation of graphs in low dimension using axis parallel boxes
• Better bounds for poset dimension and boxicity

Cites work

• A special planar satisfiability problem and a consequence of its NP- completeness
• Boxicity and treewidth
• Computing the boxicity of a graph by covering its complement by cointerval graphs
• scientific article; zbMATH DE number 3307331 (Why is no real title available?)
• Interval representations of planar graphs
• The Complexity of the Partial Order Dimension Problem

Cited in

(35)

• Boxicity of graphs with bounded degree
• Cubicity, boxicity, and vertex cover
• Boxicity of Halin graphs
• On the cubicity of interval graphs
• Covering with Euclidean boxes
• Dushnik-Miller dimension of contact systems of d-dimensional boxes
• Local boxicity
• Representability and boxicity of simplicial complexes
• Intersection dimension and graph invariants
• Characterization of the graphs with boxicity \(\leq 2\)
• Lower bounds for boxicity
• Boxicity of graphs on surfaces
• Chronological rectangle digraphs which are two-terminal series-parallel
• Cubicity, degeneracy, and crossing number
• Local boxicity and maximum degree
• On the boxicity of Kneser graphs and complements of line graphs
• Cubicity of interval graphs and the claw number
• Geometric Representation of Graphs in Low Dimension
• The frame dimension and the complete overlap dimension of a graph
• Boxicity of line graphs
• Boxicity and topological invariants
• Better bounds for poset dimension and boxicity
• On Comparable Box Dimension
• A note on lower bounds for boxicity of graphs
• Boxicity of leaf powers
• Chordal bipartite graphs with high boxicity
• Boxicity of circular arc graphs
• Grid intersection graphs and boxicity
• A survey on the boxicity and cubicity of graphs
• Bounds for boxicity of circular clique graphs and zero-divisor graphs
• A note on the intersection property for flat boxes and boxicity in \(\mathbb R^d\)
• Boxicity of a class of split graphs using words
• On the stab number of rectangle intersection graphs
• Geometric representation of graphs in low dimension using axis parallel boxes
• Boxicity and cubicity of asteroidal triple free graphs

This page was built for publication: Boxicity and maximum degree

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