Search engine for discovering works of Art, research articles, and books related to Art and Culture
ShareThis
Javascript must be enabled to continue!

Coloring, list coloring, and fractional coloring in intersections of matroids

View through CrossRef
Abstract It is known that in matroids the difference between the chromatic number and the fractional chromatic number is smaller than 1, and that the list chromatic number is equal to the chromatic number. We investigate the gap within these pairs of parameters for hypergraphs that are the intersection of a given number k of matroids. We prove that in such hypergraphs the list chromatic number is at most k times the chromatic number and at most $$2k-1$$ 2 k - 1 times the maximum chromatic number among the  k matroids. We study the relationship between three polytopes associated with k -sets of matroids, and connect them to bounds on the fractional chromatic number of the intersection of the members of the k -set. This also connects to bounds on the matroidal matching and covering number of the intersection of the members of the k -set. The tools used are in part topological.
Title: Coloring, list coloring, and fractional coloring in intersections of matroids
Description:
Abstract It is known that in matroids the difference between the chromatic number and the fractional chromatic number is smaller than 1, and that the list chromatic number is equal to the chromatic number.
We investigate the gap within these pairs of parameters for hypergraphs that are the intersection of a given number k of matroids.
We prove that in such hypergraphs the list chromatic number is at most k times the chromatic number and at most $$2k-1$$ 2 k - 1 times the maximum chromatic number among the  k matroids.
We study the relationship between three polytopes associated with k -sets of matroids, and connect them to bounds on the fractional chromatic number of the intersection of the members of the k -set.
This also connects to bounds on the matroidal matching and covering number of the intersection of the members of the k -set.
The tools used are in part topological.

Related Results

KONTESTASI TASAWUF SUNNÎ DAN TASAWUF FALSAFÎ DI NUSANTARA
KONTESTASI TASAWUF SUNNÎ DAN TASAWUF FALSAFÎ DI NUSANTARA
<p>This article scrutinizes the history of Islamic development in Nusantara between 15th to 18th centuries, which has been colored from theological mysticism thought. Uniquel...
K-Regular Matroids
K-Regular Matroids
<p>The class of matroids representable over all fields is the class of regular matroids. The class of matroids representable over all fields except perhaps GF(2) is the class...
CONJUNTURA
CONJUNTURA
<!--[if gte mso 9]><xml> <o:DocumentProperties> <o:Revision>0</o:Revision> <o:TotalTime>0</o:TotalTime> <o:Pages>1</o:Pages> &...
Matroids : h-vectors, zonotopes, and Lawrence polytopes
Matroids : h-vectors, zonotopes, and Lawrence polytopes
The main objects of study in this thesis are matroids. In particular we are interested in three particular classes matroids: regular matroids, arithmetic matroids, and internally p...
Non-Recommended Publishing Lists: Strategies for Detecting Deceitful Journals
Non-Recommended Publishing Lists: Strategies for Detecting Deceitful Journals
Abstract The rapid growth of open access publishing (OAP) has significantly improved the accessibility and dissemination of scientific knowledge. However, this expansion has also c...
Chordality in Matroids: In Search of the Converse to Hliněný's Theorem
Chordality in Matroids: In Search of the Converse to Hliněný's Theorem
<p>Bodlaender et al. [7] proved a converse to Courcelle's Theorem for graphs [15] for the class of chordal graphs of bounded treewidth. Hliněný [25] generalised Courcelle's T...
Solving Undamped and Damped Fractional Oscillators via Integral Rohit Transform
Solving Undamped and Damped Fractional Oscillators via Integral Rohit Transform
Background: The dynamics of fractional oscillators are generally described by fractional differential equations, which include the fractional derivative of the Caputo or Riemann-Li...

Back to Top