Zentralblatt MATH

Publications of (and about) Paul Erdös

Zbl.No:  591.05030
Autor:  Erdös, Paul; Füredi, Z.; Hajnal, András; Komjáth, P.; Rödl, Vojtech; Seress, Á.
Title:  Coloring graphs with locally few colors. (In English)
Source:  Discrete Math. 59, 21-34 (1986).
Review:  Authors' abstract: "Let G be a graph, m > r \geq 1 integers. Suppose that it has a good coloring with m colors which uses at most r colors in the neighborhood of every vertex. We investigate these so-called local r- colorings. One of our results (Theorem 2.4) states: The chromatic number of G, Chr(G) \leq r2r log2 log2 m and this value is the best possible in a certain sense. We consider infinite graphs as well."
Reviewer:  I.Tomescu
Classif.:  * 05C15 Chromatic theory of graphs and maps
Keywords:  strong limit cardinal; intersecting Sperner family; local r-colorings; chromatic number; infinite graphs

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag