Local and global colorability of graphs

Noga Alon, Omri Ben-Eliezer

Research output: Contribution to journalArticle

Abstract

It is shown that for any fixed c3 and r, the maximum possible chromatic number of a graph on n vertices in which every subgraph of radius at most r is c-colorable is Θ(n1r+1): it is O((n/logn)1r+1) and Ω(n1r+1/logn). The proof is based on a careful analysis of the local and global colorability of random graphs and implies, in particular, that a random n-vertex graph with the right edge probability has typically a chromatic number as above and yet most balls of radius r in it are 2-degenerate.

Original languageEnglish (US)
Pages (from-to)428-442
Number of pages15
JournalDiscrete Mathematics
Volume339
Issue number2
DOIs
StatePublished - Feb 6 2016

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Keywords

  • 2-degeneracy
  • Local chromatic number
  • Local colorability

Fingerprint Dive into the research topics of 'Local and global colorability of graphs'. Together they form a unique fingerprint.

Cite this