Scaling laws for maximum coloring of random geometric graphs
From MaRDI portal
Publication:516873
DOI10.1016/J.DAM.2016.10.009zbMATH Open1358.05096arXiv1611.05070OpenAlexW2552384179MaRDI QIDQ516873FDOQ516873
Publication date: 15 March 2017
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Abstract: We examine maximum vertex coloring of random geometric graphs, in an arbitrary but fixed dimension, with a constant number of colors. Since this problem is neither scale-invariant nor smooth, the usual methodology to obtain limit laws cannot be applied. We therefore leverage different concepts based on subadditivity to establish convergence laws for the maximum number of vertices that can be colored. For the constants that appear in these results, we provide the exact value in dimension one, and upper and lower bounds in higher dimensions.
Full work available at URL: https://arxiv.org/abs/1611.05070
Random graphs (graph-theoretic aspects) (05C80) Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Random Geometric Graphs
- The jackknife estimate of variance
- Unit disk graphs
- Graph colouring and the probabilistic method
- Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters
- Limit Theorems in Discrete Stochastic Geometry
- A matching problem and subadditive Euclidean functionals
- Subadditive Euclidean functionals and nonlinear growth in geometric probability
- Probabilistic Analysis of the Held and Karp Lower Bound for the Euclidean Traveling Salesman Problem
- On the chromatic number of random geometric graphs
Uses Software
This page was built for publication: Scaling laws for maximum coloring of random geometric graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q516873)
