✦ LIBER ✦

Boxicity of line graphs

✍ Scribed by L. Sunil Chandran; Rogers Mathew; Naveen Sivadasan

Book ID: 113567344
Publisher: Elsevier Science
Year: 2011
Tongue: English
Weight: 263 KB
Volume: 311
Category: Article
ISSN: 0012-365X
DOI: 10.1016/j.disc.2011.06.005

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Poset boxicity of graphs

✍ W.T Trotter Jr.; Douglas B West 📂 Article 📅 1987 🏛 Elsevier Science 🌐 English ⚖ 197 KB

A t-box representation of a graph encodes each vertex as a box in t-space determined by the (integer) coordinates of its lower and upper corner, such that vertices are adjacent if and only if the corresponding boxes intersect. The boxicity of a graph G is the minirmlm t for which this can be done; e

Boxicity of Circular Arc Graphs

✍ Diptendu Bhowmick; L. Sunil Chandran 📂 Article 📅 2010 🏛 Springer Japan 🌐 English ⚖ 352 KB

Boxicity of Graphs on Surfaces

✍ Louis Esperet, Gwenaël Joret 📂 Article 📅 2012 🏛 Springer Japan 🌐 English ⚖ 223 KB

Grid intersection graphs and boxicity

✍ S. Bellantoni; I. Ben-Arroyo Hartman; T. Przytycka; S. Whitesides 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 558 KB

A graph has hyuiciry k if k is the smallest integer such that G is an intersection graph of k-dimensional boxes in a &-dimensional space (where the sides of the boxes are parallel to the coordinate axis). A graph has grid dimension k if k is the smallest integer such that G is an intersection graph

Chordal Bipartite Graphs with High Boxic

Chordal Bipartite Graphs with High Boxicity

✍ L. Sunil Chandran; Mathew C. Francis; Rogers Mathew 📂 Article 📅 2011 🏛 Springer Japan 🌐 English ⚖ 186 KB

Characterization of the graphs with boxi

Characterization of the graphs with boxicity ⩽2

✍ Martin Quest; Gerd Wegner 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 360 KB

The intersection graph of a family 8TI of sets has the sets in %' as vertices and an edge between two sets iff they have nonempty intersection. Following Roberts [4] the boxicity b(G) of a graph G is defined as the smallest d such that G is the intersection graph of boxes in Euclidean d-space, i.e.