Premium
On the greatest number of 2 and 3 colorings of a (v, e)‐graph
Author(s) -
Lazebnik Felix
Publication year - 1989
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190130207
Subject(s) - combinatorics , mathematics , chromatic polynomial , graph , simple graph , upper and lower bounds , undirected graph , discrete mathematics , chromatic scale , mathematical analysis
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.