Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 32 min ago
PreprintCC BY 4.0arXiv

A note on the list chromatic number of two matroids

  • Bence Garami
Open at sourcePDFDOICite

Abstract

We study list coloring of common independent sets of two matroids. We construct a graphic matroid M1 and a partition matroid M2 with common chromatic number two and common list chromatic number three, showing that the two parameters need not be equal. This resolves a question raised by Király, later stated as a conjecture by Aharoni, Berger, Guo, and Kotlar. We also show that if two strongly base-orderable matroids are each $2$-colorable, then their intersection is $2$-list-colorable.

Related

  1. List chromatic number of G(n,r,s) graphs
    M. Koshelev
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  2. When chromatic polynomials coincide with list-color functions: a threshold linear in the maximum degree
    Meiqiao Zhang, Fengming Dong
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. Chromatic word-quasisymmetric functions of matroids
    Raul Penaguiao, Sophie Rehberg
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. A note on decompositions into 3-chromatic graphs
    Bertille Granet, Daniel Horsley, Jeffrey N. Santrio
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. On the k-Distance Chromatic Number of Unicyclic Graphs
    Rosário Fernandes, Rúben Palma
    Discrete Mathematics LettersPeer-reviewedCC BYFull textGeneral mathematicsDOAJ

Cite

BibTeXRIS
BibTeX
@misc{garami2026note,
  title = {{A note on the list chromatic number of two matroids}},
  author = {Bence Garami},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.07318},
  eprint = {2610.07318},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.07318},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - A note on the list chromatic number of two matroids
AU  - Bence Garami
PY  - 2026
DA  - 2026/10/05
PB  - arXiv
DO  - 10.48550/arxiv.2610.07318
UR  - https://arxiv.org/abs/2610.07318
AB  - We study list coloring of common independent sets of two matroids. We construct a graphic matroid M_1 and a partition matroid M_2 with common chromatic number two and common list chromatic number three, showing that the two parameters need not be equal. This resolves a question raised by Király, later stated as a conjecture by Aharoni, Berger, Guo, and Kotlar. We also show that if two strongly base-orderable matroids are each $2$-colorable, then their intersection is $2$-list-colorable.
ER  -