Scholarlink

<p>We characterize all orientations of cycles <i>C</i> for which for every fixed <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(\varepsilon &gt; 0\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>ε</mi> <mo>&gt;</mo> <mn>0</mn> </mrow> </math></EquationSource> </InlineEquation> there exists a constant <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(c \ge 1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>c</mi> <mo>≥</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation> such that every digraph <i>D</i> without loops or parallel arcs with <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(\chi (D) \ge c\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>χ</mi> <mo stretchy="false">(</mo> <mi>D</mi> <mo stretchy="false">)</mo> <mo>≥</mo> <mi>c</mi> </mrow> </math></EquationSource> </InlineEquation> and minimum out-degree at least <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(\varepsilon |V(D)|\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>ε</mi> <mo stretchy="false">|</mo> <mi>V</mi> <mo stretchy="false">(</mo> <mi>D</mi> <mo stretchy="false">)</mo> <mo stretchy="false">|</mo> </mrow> </math></EquationSource> </InlineEquation> contains <i>C</i> as a subdigraph. This generalizes a result of Thomassen.</p>

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

Orientations of Cycles in Digraphs of High Chromatic Number and High Minimum Out-Degree

  • 期刊论文

  • 发表日期：

    2026年3月4日

查看全文
  • Hidde Koerts,
  • Benjamin Moore,
  • Sophie Spirkl

摘要

We characterize all orientations of cycles C for which for every fixed \(\varepsilon > 0\) ε > 0 there exists a constant \(c \ge 1\) c ≥ 1 such that every digraph D without loops or parallel arcs with \(\chi (D) \ge c\) χ ( D ) ≥ c and minimum out-degree at least \(\varepsilon |V(D)|\) ε | V ( D ) | contains C as a subdigraph. This generalizes a result of Thomassen.