Spectrum of graph parameters

Abstract

Let G be the class of all graphs and J⊆G . A graph parameter f is called an interpolation graph parameter with respect to J if there exist integers a and b such that {f(G):G ∈J} = {k ∈ ZZ:a ≤ k ≤b}. In the study of interpolation on graph parameter f with respect to J, we may consider into two parts. First, it is to consider whether a given graph parameter f interpolates with respect to J or not. If it is, we shall develop techniques to find min(f,J) := min {f(G):G ∈J}and max(f,J) := max {f(G):G ∈J} . We discuss various kinds of graph parameters and answer the first part of interpolation theorem of graph parameters. Some of which have been done while some are new. As an application, we are able to provide an alternate proof of Erd˝os’ conjecture on regular graphs with prescribed chromatic number.