Coloring the intersection of two matroids
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910917522882560 |
|---|---|
| author | Berger, Eli Guo, He |
| author_facet | Berger, Eli Guo, He |
| contents | A result [The intersection of a matroid and a simplicial complex, Trans. Amer. Math. Soc. 358] from 2006 of Aharoni and the first author of this paper states that for any two positive integers $p,q$, where $p$ divides $q$, if a matroid $\mathcal{M}$ is $p$-colorable and a matroid $\mathcal{N}$ is $q$-colorable then $\mathcal{M} \cap \mathcal{N}$ is $(p+q)$-colorable. In this paper we show that the assumption that $p$ divides $q$ is in fact redundant, and we also prove that $\mathcal{M} \cap \mathcal{N}$ is even $p+q$ list-colorable.
The result uses topology and relies on a new parameter yielding a lower bound for the topological connectivity of the intersection of two matroids. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_09160 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Coloring the intersection of two matroids Berger, Eli Guo, He Combinatorics Algebraic Topology 05B35, 05C15, 05C10, 57M15 A result [The intersection of a matroid and a simplicial complex, Trans. Amer. Math. Soc. 358] from 2006 of Aharoni and the first author of this paper states that for any two positive integers $p,q$, where $p$ divides $q$, if a matroid $\mathcal{M}$ is $p$-colorable and a matroid $\mathcal{N}$ is $q$-colorable then $\mathcal{M} \cap \mathcal{N}$ is $(p+q)$-colorable. In this paper we show that the assumption that $p$ divides $q$ is in fact redundant, and we also prove that $\mathcal{M} \cap \mathcal{N}$ is even $p+q$ list-colorable. The result uses topology and relies on a new parameter yielding a lower bound for the topological connectivity of the intersection of two matroids. |
| title | Coloring the intersection of two matroids |
| topic | Combinatorics Algebraic Topology 05B35, 05C15, 05C10, 57M15 |
| url | https://arxiv.org/abs/2407.09160 |