Local and global colorability of graphs

DOI10.1016/J.DISC.2015.09.006zbMATH Open1327.05097arXiv1410.6236OpenAlexW1824385373MaRDI QIDQ898084FDOQ898084

Authors: Omri Ben-Eliezer, Noga Alon 

Publication date: 8 December 2015

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

Abstract: It is shown that for any fixed $cgeq3$ 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 $ildeThetaleft(n^{frac1r+1}ight)$ (that is, $n^{f}rac1r+1$ up to a factor poly-logarithmic in $n$). 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.

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

Recommendations

• On coloring graphs with locally small chromatic number
• On the chromatic number of random graphs
• Coloring graphs with locally few colors
• On the chromatic number of random graphs
• scientific article; zbMATH DE number 861409

zbMATH Keywords

local chromatic number2-degeneracylocal colorability

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Graph Theory and Probability
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• The Ramsey number R(3, t) has order of magnitude t²/log t
• A note on Ramsey numbers
• Cliques in random graphs
• Bounding Ramsey numbers through large deviation inequalities
• Independence numbers of locally sparse graphs and a Ramsey type problem
• On circuits and subgraphs of chromatic graphs
• On coloring graphs with locally small chromatic number

Cited In (3)

• On coloring graphs with locally small chromatic number
• Title not available (Why is that?)
• NP-completeness of local colorings of graphs

This page was built for publication: Local and global colorability of graphs

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