Scaling laws for maximum coloring of random geometric graphs

Sem Borst, Milan Bradonjić

Research output: Contribution to journalArticleAcademicpeer-review

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.

Original languageEnglish
Pages (from-to)427-437
Number of pages11
JournalDiscrete Applied Mathematics
Volume217
DOIs
Publication statusPublished - 30 Jan 2017

Bibliographical note

Publisher Copyright:
© 2016 Elsevier B.V.

Keywords

  • Asymptotic laws
  • Coloring
  • Random geometric graphs

Fingerprint

Dive into the research topics of 'Scaling laws for maximum coloring of random geometric graphs'. Together they form a unique fingerprint.

Cite this