Ball packings with high chromatic numbers from strongly regular graphs

DOI10.1016/J.DISC.2017.03.006zbMATH Open1361.05140arXiv1502.02070OpenAlexW2147517455MaRDI QIDQ526257FDOQ526257

Hao Chen

Publication date: 10 May 2017

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

Abstract: Inspired by Bondarenko's counter-example to Borsuk's conjecture, we notice some strongly regular graphs that provide examples of ball packings whose chromatic numbers are significantly higher than the dimensions. In particular, from generalized quadrangles we obtain unit ball packings in dimension $q^3-q^2+q$ with chromatic number $q^3+1$, where $q$ is a prime power. This improves the previous lower bound for the chromatic number of ball packings.

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

Recommendations

• Obstructions to the realization of distance graphs with large chromatic numbers on spheres of small radii
• Counterexamples to Borsuk's conjecture with large girth
• On lower bounds for the chromatic number of spheres
• Borsuk's problem and the chromatic numbers of some metric spaces
• On the colouring of spheres embedded in \(\mathbb R^n\)

zbMATH Keywords

chromatic numberstrongly regular graphsball packinggeneralized quadrangles

Mathematics Subject Classification ID

Association schemes, strongly regular graphs (05E30) Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Title not available (Why is that?)
• Distance regular graphs of diameter 3 and strongly regular graphs
• Intersection theorems with geometric consequences
• A counterexample to Borsuk’s conjecture
• Title not available (Why is that?)
• Finite generalized quadrangles
• Title not available (Why is that?)
• Spreads in strongly regular graphs
• Strongly regular graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Spreads and ovoids in finite generalized quadrangles
• On a family of strongly regular graphs with \(\lambda = 1\)
• Strongly regular graphs having strongly regular subconstituents
• Title not available (Why is that?)
• Matroidal bijections between graphs
• On Borsuk's conjecture for two-distance sets
• A 64-dimensional counterexample to Borsuk's conjecture
• Higher-Dimensional Analogues of the Map Coloring Problem
• On rank 3 permutation groups
• The regular two-graph on 276 vertices
• Packings with large minimum kissing numbers
• The Hermitian two-graph and its code
• Binary codes of some strongly regular subgraphs of the McLaughlin graph
• On configurations of solid balls in 3-space: chromatic numbers and knotted cycles
• Classification of some strongly regular subgraphs of the McLaughlin graph
• Title not available (Why is that?)

Cited In (2)

• Geometry and topology of symmetric point arrangements
• Contact graphs of ball packings

Uses Software

• MathOverflow

This page was built for publication: Ball packings with high chromatic numbers from strongly regular graphs

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