Cubicity, boxicity, and vertex cover

DOI10.1016/j.disc.2008.06.003zbMath1184.05094arXiv0712.2688OpenAlexW2134744951MaRDI QIDQ1025509

Anita Das, Chintan D. Shah, L. Sunil Chandran

Publication date: 19 June 2009

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

Full work available at URL: https://arxiv.org/abs/0712.2688

zbMATH Keywords

vertex coverboxicitycubicity

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items

Ferrers dimension of grid intersection graphs ⋮ Boxicity of line graphs ⋮ Cubicity and bandwidth ⋮ Sublinear approximation algorithms for boxicity and related problems ⋮ Boxicity of circular arc graphs ⋮ Boxicity and cubicity of asteroidal triple free graphs ⋮ A constant factor approximation algorithm for boxicity of circular arc graphs ⋮ 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
• Geometric representation of graphs in low dimension using axis parallel boxes
• The cubicity of hypercube graphs
• On the cubicity of certain graphs
• Interval representations of planar graphs
• Sphericity exceeds cubicity for almost all complete bipartite graphs
• A characterization of Robert's inequality for boxicity
• A special planar satisfiability problem and a consequence of its NP- completeness
• Boxicity and maximum degree
• Sphericity, cubicity, and edge clique covers of graphs
• Boxicity and treewidth
• The Complexity of the Partial Order Dimension Problem
• Reducibility among Combinatorial Problems
• Sphere-of-influence graphs using the sup-norm