Boxicity of line graphs

DOI10.1016/J.DISC.2011.06.005MaRDI QIDQ409342zbMATH OpenOpenAlexFDO

Authors L. Sunil Chandran, Rogers Mathew, Naveen Sivadasan

Publication date 13 April 2012

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

hypercubeline graphintersection graphinterval graphsubdivisionboxicityedge graph

Mathematics Subject Classification ID

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

Abstract: Boxicity of a graph H, denoted by box(H), is the minimum integer k such that H is an intersection graph of axis-parallel k-dimensional boxes in R^k. In this paper, we show that for a line graph G of a multigraph, box(G) <= 2Delta(lceil log_2(log_2(Delta)) ceil + 3) + 1, where Delta denotes the maximum degree of G. Since Delta <= 2(chi - 1), for any line graph G with chromatic number chi, box(G) = O(chi log_2(log_2(chi))). For the d-dimensional hypercube H_d, we prove that box(H_d) >= (lceil log_2(log_2(d)) ceil + 1)/2. The question of finding a non-trivial lower bound for box(H_d) was left open by Chandran and Sivadasan in [L. Sunil Chandran and Naveen Sivadasan. The cubicity of Hypercube Graphs. Discrete Mathematics, 308(23):5795-5800, 2008]. The above results are consequences of bounds that we obtain for the boxicity of fully subdivided graphs (a graph which can be obtained by subdividing every edge of a graph exactly once).

Recommendations

• Boxicity and maximum degree
• Boxicity of graphs with bounded degree
• Cubicity, boxicity, and vertex cover
• Geometric Representation of Graphs in Low Dimension
• An upper bound for cubicity in terms of boxicity

Cites work

• scientific article; zbMATH DE number 1432797 (Why is no real title available?)
• scientific article; zbMATH DE number 3307331 (Why is no real title available?)
• A special planar satisfiability problem and a consequence of its NP- completeness
• Boxicity and cubicity of asteroidal triple free graphs
• Boxicity and maximum degree
• Boxicity and treewidth
• Boxicity of circular arc graphs
• Boxicity of graphs with bounded degree
• Boxicity of leaf powers
• Chordal bipartite graphs with high boxicity
• Computing the boxicity of a graph by covering its complement by cointerval graphs
• Cubicity, boxicity, and vertex cover
• Geometric representation of graphs in low dimension using axis parallel boxes
• Interval representations of planar graphs
• Minimal scrambling sets of simple orders
• The Complexity of the Partial Order Dimension Problem
• The cubicity of hypercube graphs

Cited in

(12)

• Boxicity of circular arc graphs
• Cubicity, degeneracy, and crossing number
• A note on lower bounds for boxicity of graphs
• On the boxicity of Kneser graphs and complements of line graphs
• Covering with Euclidean boxes
• Separation dimension and degree
• Boxicity of graphs with bounded degree
• Bounds for the boxicity of Mycielski graphs
• Local boxicity and maximum degree
• Boxicity and cubicity of product graphs
• Perfect and nearly perfect separation dimension of complete and random graphs
• Separation dimension of graphs and hypergraphs

This page was built for publication: Boxicity of line graphs

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