Scholarlink

<p>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 <i>k</i> of matroids. We prove that in such hypergraphs the list chromatic number is at most <i>k</i> times the chromatic number and at most <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="493_2025_178_Article_IEq1.gif" Format="GIF" Height="15" Rendition="HTML" Resolution="72" Type="Linedraw" Width="48" /> </InlineMediaObject> <EquationSource Format="TEX">\(2k-1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>2</mn> <mi>k</mi> <mo>-</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation> times the maximum chromatic number among the&#xa0;<i>k</i> matroids. We study the relationship between three polytopes associated with <i>k</i>-sets of matroids, and connect them to bounds on the fractional chromatic number of the intersection of the members of the <i>k</i>-set. This also connects to bounds on the matroidal matching and covering number of the intersection of the members of the <i>k</i>-set. The tools used are in part topological.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

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

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2025年9月25日

查看全文
  • Ron Aharoni,
  • Eli Berger,
  • He Guo,
  • Dani Kotlar

摘要

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.