Local and global colorability of graphs

DOI10.1016/J.DISC.2015.09.006MaRDI QIDQ898084zbMATH OpenOpenAlexFDO

Authors Omri Ben-Eliezer, Noga Alon

Publication date 8 December 2015

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

2-degeneracylocal chromatic numberlocal colorability

Mathematics Subject Classification ID

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

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.

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

Cites work

• A note on Ramsey numbers
• Bounding Ramsey numbers through large deviation inequalities
• Cliques in random graphs
• Graph Theory and Probability
• 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
• 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

Cited in

(3)

• NP-completeness of local colorings of graphs
• scientific article; zbMATH DE number 2097236 (Why is no real title available?)
• On coloring graphs with locally small chromatic number

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)