Boxicity of line graphs

Chandran, L S and Mathew, R and Sivadasan, N (2011) Boxicity of line graphs. Discrete Mathematics, 311 (21). pp. 2359-2367. ISSN 0012-365X

Full text not available from this repository. (Request a copy)

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

[error in script]
IITH Creators:
IITH CreatorsORCiD
Sivadasan, NUNSPECIFIED
Item Type: Article
Uncontrolled Keywords: Boxicity; Edge graph; Hypercube; Intersection graph; Interval graph; Line graph; Subdivision
Subjects: ?? sub3.8 ??
Computer science > Big Data Analytics
Divisions: Department of Computer Science & Engineering
Depositing User: Team Library
Date Deposited: 29 Oct 2014 09:43
Last Modified: 13 Apr 2015 06:44
URI: http://raiith.iith.ac.in/id/eprint/527
Publisher URL: http://dx.doi.org/10.1016/j.disc.2011.06.005
OA policy: http://www.sherpa.ac.uk/romeo/issn/0012-365X/
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 527 Statistics for this ePrint Item