Boxicity and separation dimension

DOI10.1007/978-3-319-12340-0_7MaRDI QIDQ2945181zbMATH OpenOpenAlexFDO

Authors Manu Basavaraju, L. Sunil Chandran, Rogers Mathew, Deepak Rajendraprasad, Martin Charles Golumbic

Publication date 9 September 2015

Published in Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

line graphboxicityacyclic chromatic numberscrambling permutationseparation dimension

Mathematics Subject Classification ID

Hypergraphs (05C65) Graph operations (line graphs, products, etc.) (05C76)

Abstract: A family $mathcalF$ of permutations of the vertices of a hypergraph $H$ is called 'pairwise suitable' for $H$ if, for every pair of disjoint edges in $H$, there exists a permutation in $mathcalF$ in which all the vertices in one edge precede those in the other. The cardinality of a smallest such family of permutations for $H$ is called the 'separation dimension' of $H$ and is denoted by $pi(H)$. Equivalently, $pi(H)$ is the smallest natural number $k$ so that the vertices of $H$ can be embedded in $mathbb{R}^k$ such that any two disjoint edges of $H$ can be separated by a hyperplane normal to one of the axes. We show that the separation dimension of a hypergraph $H$ is equal to the 'boxicity' of the line graph of $H$. This connection helps us in borrowing results and techniques from the extensive literature on boxicity to study the concept of separation dimension.

Recommendations

• Separation dimension of graphs and hypergraphs
• Separation dimension and sparsity
• Separation dimension and degree
• Separation dimension of bounded degree graphs
• Dimensions of hypergraphs

Cited in

(13)

• Separation dimension and sparsity
• Box dimension of Neimark–Sacker bifurcation
• The induced separation dimension of a graph
• Separation dimension of graphs and hypergraphs
• Fractional and circular separation dimension of graphs
• Separation dimension and degree
• Lower bounds for boxicity
• Dimensions of hypergraphs
• Perfect and nearly perfect separation dimension of complete and random graphs
• Separation dimension of bounded degree graphs
• Induced separation dimension
• Covering small subgraphs of (hyper)tournaments with spanning acyclic subgraphs
• Sequence Covering Arrays and Linear Extensions

This page was built for publication: Boxicity and separation dimension

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2945181)