Decomposition of graph functions

AbstractThe V-functions of Tutte [1] are generalized to U-functions on graphs with a distinguished subset of vertices. The class of U-functions of two variables generalize dichromatic polynomials as well as the W-functions defined by Tutte [2]. The values of U-functions on a graph G are characterized in terms of spanning subgraphs of G and also in terms of collections of simple graphs constructed from G. Decompositions of dichromatic polynomials as well as dichromatic U-functions are obtained in terms of decompositions of G