Decomposable polymatroids and connections with graph coloring

DOI10.1016/J.EJC.2020.103179MaRDI QIDQ2198995zbMATH OpenOpenAlexFDO

Authors Carolyn Chun, Joseph E. Bonin

Publication date 15 September 2020

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1908.09030

zbMATH Keywords

chromatic numberchromatic polynomials

Mathematics Subject Classification ID

Graph polynomials (05C31) Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40) Combinatorial aspects of matroids and geometric lattices (05B35) Coloring of graphs and hypergraphs (05C15)

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.

Recommendations

• A geometric theory of hypergraph colouring
• A NOTE ON THE DECOMPOSITION OF POLY-LINKING SYSTEMS AND THE MINORS OF GENERALIZED POLYMATROIDS
• Uniqueness of the decomposition of the rank function of a 2-polymatroid
• A decomposition theorem for the linking polynomial of two matroids
• Recognizing Polymatroids Associated with Hypergraphs

Cites work

• scientific article; zbMATH DE number 3959442 (Why is no real title available?)
• scientific article; zbMATH DE number 3468904 (Why is no real title available?)
• scientific article; zbMATH DE number 3639645 (Why is no real title available?)
• scientific article; zbMATH DE number 5873618 (Why is no real title available?)
• Branch-width and Rota's conjecture
• Deletion-contraction to form a polymatroid
• Discrete polymatroids
• Excluded minors for Boolean polymatroids
• On the connectivity function of a binary matroid
• Some excluded-minor theorems for a class of polymatroids
• The reconstruction of a matroid from its connectivity function
• Uniqueness of the decomposition of the rank function of a 2-polymatroid

Cited in

(7)

• scientific article; zbMATH DE number 5722310 (Why is no real title available?)
• Uniqueness of the decomposition of the rank function of a 2-polymatroid
• Partial coloring, vertex decomposability and sequentially Cohen-Macaulay simplicial complexes
• scientific article; zbMATH DE number 973934 (Why is no real title available?)
• The Excluded Minors for Three Classes of 2-Polymatroids Having Special Types of Natural Matroids
• Colored Modular and Split Decompositions of Graphs with Applications to Trigraphs
• The Natural Matroid of an Integer Polymatroid

This page was built for publication: Decomposable polymatroids and connections with graph coloring

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2198995)