Boxicity of line graphs

DOI10.1016/J.DISC.2011.06.005zbMATH Open1239.05158arXiv1009.4471OpenAlexW1681153136MaRDI QIDQ409342FDOQ409342

L. Sunil Chandran, Naveen Sivadasan, Rogers Mathew

Publication date: 13 April 2012

Published in: Discrete Mathematics (Search for Journal in Brave)

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).

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)

Cites Work

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

Cited In (9)

• Boxicity of circular arc graphs
• Bounds for the boxicity of Mycielski graphs
• Cubicity, degeneracy, and crossing number
• Separation dimension of graphs and hypergraphs
• Separation dimension and degree
• Boxicity and cubicity of product graphs
• Covering with Euclidean boxes
• Perfect and nearly perfect separation dimension of complete and random graphs
• Local boxicity and maximum degree

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)