Coloring, list coloring, and fractional coloring in intersections of matroids
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866913806178844672 |
|---|---|
| author | Aharoni, Ron Berger, Eli Guo, He Kotlar, Dani |
| author_facet | Aharoni, Ron Berger, Eli Guo, He Kotlar, Dani |
| contents | 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 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_08789 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Coloring, list coloring, and fractional coloring in intersections of matroids Aharoni, Ron Berger, Eli Guo, He Kotlar, Dani Combinatorics Algebraic Topology 05B35, 05C15, 05C10, 57M15, 52B40, 05C70, 90C27, 05C72 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 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 |
| topic | Combinatorics Algebraic Topology 05B35, 05C15, 05C10, 57M15, 52B40, 05C70, 90C27, 05C72 |
| url | https://arxiv.org/abs/2407.08789 |