Header menu link for other important links
X
Boxicity of line graphs
L.S. Chandran, , N. Sivadasan
Published in Elsevier B.V.
2011
Volume: 311
   
Issue: 21
Pages: 2359 - 2367
Abstract
The 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 Rk. In this paper we show that for a line graph G of a multigraph, box(G)≤2Δ(G)(log2log2Δ(G)⌉+3)+1, where Δ(G) denotes the maximum degree of G. Since G is a line graph, Δ(G)≤2(χ(G)-1), where χ(G) denotes the chromatic number of G, and therefore, box(G)=O(χ(G)log2log2(χ(G))). For the d-dimensional hypercube Qd, we prove that box( Qd)<12(log2log2d⌉+1). The question of finding a nontrivial lower bound for box(Qd) was left open by Chandran and Sivadasan in [L. Sunil Chandran, Naveen Sivadasan, The cubicity of Hypercube Graphs. Discrete Mathematics 308 (23) (2008) 57955800]. The above results are consequences of bounds that we obtain for the boxicity of a fully subdivided graph (a graph that can be obtained by subdividing every edge of a graph exactly once). © 2011 Elsevier B.V. All rights reserved.
About the journal
JournalData powered by TypesetDiscrete Mathematics
PublisherData powered by TypesetElsevier B.V.
ISSN0012365X