Journal article icon

Journal article

Separation dimension and degree

Abstract:

The separation dimension of a graph G is the minimum positive integer d for which there is an embedding of G into ℝ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 Δ has separation dimension less than 20Δ, which is best possible up to a constant factor. We also prove that graphs with separation dimension 3 have bounded average degree and b...

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed

Actions


Access Document


Files:
Publisher copy:
10.1017/S0305004119000525

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Mathematical Institute
Oxford college:
Merton College
Role:
Author
ORCID:
0000-0003-4489-5988
More from this funder
Name:
Leverhulme Trust
Grant:
RF-2017-093\9
Publisher:
Cambridge University Press
Journal:
Mathematical Proceedings of the Cambridge Philosophical Society More from this journal
Volume:
170
Issue:
3
Pages:
549-558
Publication date:
2019-11-22
Acceptance date:
2019-10-14
DOI:
EISSN:
1469-8064
ISSN:
0305-0041
Language:
English
Keywords:
Pubs id:
pubs:1070392
UUID:
uuid:07e81428-b618-45fc-b952-1775d4cf31b2
Local pid:
pubs:1070392
Source identifiers:
1070392
Deposit date:
2019-11-07

Terms of use


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP