Decomposable polymatroids and connections with graph coloring

DOI10.1016/J.EJC.2020.103179zbMATH Open1447.05047arXiv1908.09030OpenAlexW3038101661MaRDI QIDQ2198995FDOQ2198995

Authors: Carolyn Chun, Joseph E. Bonin 

Publication date: 15 September 2020

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Branch-width and Rota's conjecture
• Title not available (Why is that?)
• The reconstruction of a matroid from its connectivity function
• Discrete polymatroids
• Title not available (Why is that?)
• Deletion-contraction to form a polymatroid
• Excluded minors for Boolean polymatroids
• Title not available (Why is that?)
• Some excluded-minor theorems for a class of polymatroids
• On the connectivity function of a binary matroid
• Uniqueness of the decomposition of the rank function of a 2-polymatroid

Cited In (7)

• Title not available (Why is that?)
• Uniqueness of the decomposition of the rank function of a 2-polymatroid
• Title not available (Why is that?)
• Partial coloring, vertex decomposability and sequentially Cohen-Macaulay simplicial complexes
• 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)