Some new bounds for the maximum number of vertex colorings of a (v,e)-graph
Owen D. Byer · Journal of Graph Theory · 1998
Let f(v, e, λ) denote the maximum number of proper vertex colorings of a graph with v vertices and e edges in λ colors. In this paper we present some new upper bounds for f(v, e, λ). In particular, a new notion of pseudo-proper colorings of a graph is given, which allows us to significantly improve the upper bounds for f(v, e, 3) given by Lazebnik and Liu in the case where e > v2/4. © 1998 John Wiley & Sons, Inc. J. Graph Theory 28: 115–128, 1998