Coloring graphs with locally few colors
β
P ErdΓΆs; Z FΓΌredi; A Hajnal; P KomjΓ‘th; V RΓΆdl; Γ Seress
π
Article
π
1986
π
Elsevier Science
π
English
β 832 KB
Let G be a graph, m > r t> 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) ~< r2" log21og2 m (an