Boxicity of line graphs

DOI10.1016/j.disc.2011.06.005zbMath1239.05158arXiv1009.4471OpenAlexW1681153136MaRDI QIDQ409342

L. Sunil Chandran, Naveen Sivadasan, Rogers Mathew

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

hypercubeintersection graphsubdivisionline graphinterval graphboxicityedge graph

Mathematics Subject Classification ID

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

Related Items (7)

Separation dimension of graphs and hypergraphs ⋮ Local boxicity and maximum degree ⋮ Perfect and nearly perfect separation dimension of complete and random graphs ⋮ Cubicity, degeneracy, and crossing number ⋮ Separation dimension and degree ⋮ Bounds for the boxicity of Mycielski graphs ⋮ Boxicity and cubicity of product graphs

Cites Work

• Unnamed Item
• Unnamed Item
• 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
• Boxicity of graphs with bounded degree
• Cubicity, boxicity, and vertex cover
• Interval representations of planar graphs
• A special planar satisfiability problem and a consequence of its NP- completeness
• Boxicity and maximum degree
• Boxicity and treewidth
• The Complexity of the Partial Order Dimension Problem
• Minimal scrambling sets of simple orders
• Boxicity and Poset Dimension

This page was built for publication: Boxicity of line graphs