Decomposable polymatroids and connections with graph coloring. (October 2020)

• Record Type: Journal Article
• Authors: Bonin, Joseph E.; Chun, Carolyn
• Is Part Of: European journal of combinatorics. Volume 89(2020)
• Publication Date: 2020-10
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2020.103179
• Languages: English
• ISSNs: 0195-6698

Abstract

Abstract: We introduce ideas that complement the many known connections between polymatroids and graph coloring. Given a hypergraph that satisfies certain conditions, we construct polymatroids, given as rank functions, that can be written as sums of rank functions of matroids, and for which the minimum number of matroids required in such sums is the chromatic number of the line graph of the hypergraph. This result motivates introducing chromatic numbers and chromatic polynomials for polymatroids. We show that the chromatic polynomial of any 2-polymatroid is a rational multiple of the chromatic polynomial of some graph. We also find the excluded minors for the minor-closed class of polymatroids that can be written as sums of rank functions of matroids that form a chain of quotients.