Erdős, Paul; Füredi, Z.; Hajnal, András; Komjáth, P.; Rödl, Vojtěch; Seress, Á. Coloring graphs with locally few colors. (English) Zbl 0591.05030 Discrete Math. 59, 21-34 (1986). 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 r2^r \log_2 \log_2 m\) and this value is the best possible in a certain sense. We consider infinite graphs as well.” Reviewer: I.Tomescu Cited in 7 ReviewsCited in 26 Documents MSC: 05C15 Coloring of graphs and hypergraphs Keywords:strong limit cardinal; intersecting Sperner family; local r-colorings; chromatic number; infinite graphs PDFBibTeX XMLCite \textit{P. Erdős} et al., Discrete Math. 59, 21--34 (1986; Zbl 0591.05030) Full Text: DOI References: [1] Erdös, P., Graph theory and probability, Canad. J. Math., 11, 34-38 (1959) · Zbl 0084.39602 [2] P. Erdös, P. Frankl and Z. Füredi, Families of finite sets in which no set is covered by the union of \(r\); P. Erdös, P. Frankl and Z. Füredi, Families of finite sets in which no set is covered by the union of \(r\) [3] Erdös, P.; Hajnal, A., On chromatic number of graphs and set-systems, Acta Math. Acad. Sci. Hung., 17, 61-99 (1966) · Zbl 0151.33701 [4] Erdös, P.; Hajnal, A., On chromatic number of infinite graphs, (Erdös, P.; Katona, G., Theory of Graphs, Proc. Coll. Tihany 1966 (1968), Akadémiai Kiadó), 83-89 [5] Erdös, P.; Hindman, N., Enumeration of intersecting families, Discrete Math., 48, 61-65 (1984) · Zbl 0529.05044 [6] Erdös, P.; Szekeres, G., A combinatorial problem in geometry, Compositio Math., 2, 463-470 (1935) · JFM 61.0651.04 [7] Hausdorff, F., Über zwei Sätze von G. Fichtenholz und L. Kantorovitch, Studia Math., 6, 18-19 (1936) · JFM 62.1064.01 [8] Katona, G.; Nemetz, T.; Simonovits, M., On a graph-problem of Turán, Mat. Lapok, 15, 228-238 (1964), in Hungarian · Zbl 0138.19402 [9] Kleitman, D. J.; Spencer, J., Families of \(k\)-independent sets, Discrete Math., 6, 255-262 (1973) · Zbl 0269.05002 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.