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