On the greatest number of 2 and 3 colorings of a (v, e)‐graph
Felix Lazebnik · Journal of Graph Theory · 1989
Abstract Let F denote the family of simple undirected graphs on v vertices having e edges (( v, e )‐graphs) and P (λ, G ) be the chromatic polynomial of a graph G . For the given integers v , e, Δ, let f ( v, e, Δ) denote the greatest number of proper colorings in Δ or less colors that a (v, e)‐graph G can have, i.e., f(v, e, Δ) = max{P(Δ, G): G ∈ F}. In this paper we determine f(v, e , 2) and describe all graphs G for which P (2, G ) = f ( v, e , 2). For f ( v, e , 3), a lower bound and an upper bound are found.