Separation dimension and degree

DOI10.1017/S0305004119000525MaRDI QIDQ4958696zbMATH OpenOpenAlexFDO

Authors David R. Wood, Alex Scott

Publication date 14 September 2021

Published in Mathematical Proceedings of the Cambridge Philosophical Society (Search for Journal in Brave)

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

zbMATH Keywords

maximum average degreestrongly separating representation

Mathematics Subject Classification ID

Vertex degrees (05C07) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Graph representations (geometric and intersection representations, etc.) (05C62)

Abstract: The "separation dimension" of a graph $G$ is the minimum positive integer $d$ for which there is an embedding of $G$ into $mathbb{R}^d$, such that every pair of disjoint edges are separated by some axis-parallel hyperplane. We prove a conjecture of Alon et al. [SIAM J. Discrete Math. 2015] by showing that every graph with maximum degree $Delta$ has separation dimension less than $20Delta$, which is best possible up to a constant factor. We also prove that graphs with separation dimension 3 have bounded average degree and bounded chromatic number, partially resolving an open problem by Alon et al. [J. Graph Theory 2018].

Recommendations

• Separation dimension of bounded degree graphs
• Separation dimension and sparsity
• Separation dimension of graphs and hypergraphs
• Fractional and circular separation dimension of graphs
• Boxicity and separation dimension

Cites work

• Asymptotically optimal frugal colouring
• Better bounds for poset dimension and boxicity
• Boxicity and separation dimension
• Boxicity of line graphs
• Circular separation dimension of a subclass of planar graphs
• Colouring a graph frugally
• Fractional and circular separation dimension of graphs
• Frugal, acyclic and star colourings of graphs
• scientific article; zbMATH DE number 3492718 (Why is no real title available?)
• On the dimensions of ordered sets of bounded degree
• Probability and Computing
• Separation dimension and sparsity
• Separation dimension of bounded degree graphs
• Separation dimension of graphs and hypergraphs
• The induced separation dimension of a graph
• The star arboricity of graphs

Cited in

(14)

• Separability and distance
• Fractional and circular separation dimension of graphs
• Boxicity and separation dimension
• Separation dimension of graphs and hypergraphs
• Separation index of a graph
• Induced separation dimension
• Separation dimension of bounded degree graphs
• scientific article; zbMATH DE number 4029630 (Why is no real title available?)
• Separation dimension and sparsity
• Circular separation dimension of a subclass of planar graphs
• Perfect and nearly perfect separation dimension of complete and random graphs
• Coloring lines and Delaunay graphs with respect to boxes
• A survey on the boxicity and cubicity of graphs
• The induced separation dimension of a graph

This page was built for publication: Separation dimension and degree

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