<p>Steiner (JGT 2024) proved that given a digraph <i>F</i> and pairs of integers <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\((r_e, q_e)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <msub> <mi>r</mi> <mi>e</mi> </msub> <mo>,</mo> <msub> <mi>q</mi> <mi>e</mi> </msub> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> with <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(q_e\ge 2\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>q</mi> <mi>e</mi> </msub> <mo>≥</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation> for every arc <i>e</i> of <i>F</i>, there is an integer <i>N</i> such that every digraph of dichromatic number at least <i>N</i> contains a subdivision of <i>F</i> in which for every arc <i>e</i> of <i>F</i>, the corresponding branching path has length <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(r_e\pmod {q_e}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>r</mi> <mi>e</mi> </msub> <mspace width="4.44443pt" /> <mrow> <mo stretchy="false">(</mo> <mo>mod</mo> <mspace width="0.277778em" /> <msub> <mi>q</mi> <mi>e</mi> </msub> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>. We extend this result to directed cycles containing a specified set of arcs. We show that given such <i>F</i> and <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(\{(r_e, q_e)\}_{e\in A(F)}\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mrow> <mo stretchy="false">{</mo> <mrow> <mo stretchy="false">(</mo> <msub> <mi>r</mi> <mi>e</mi> </msub> <mo>,</mo> <msub> <mi>q</mi> <mi>e</mi> </msub> <mo stretchy="false">)</mo> </mrow> <mo stretchy="false">}</mo> </mrow> <mrow> <mi>e</mi> <mo>∈</mo> <mi>A</mi> <mo stretchy="false">(</mo> <mi>F</mi> <mo stretchy="false">)</mo> </mrow> </msub> </math></EquationSource> </InlineEquation>, there is an integer <i>N</i> such that if the minimum number of parts in a vertex partition <InlineEquation ID="IEq5"> <EquationSource Format="TEX">\(\mathcal {P}\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">P</mi> </math></EquationSource> </InlineEquation> of a digraph&#xa0;<i>D</i> such that each part has no directed cycles containing an arc of <InlineEquation ID="IEq6"> <EquationSource Format="TEX">\(Z\subseteq A(D)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>Z</mi> <mo>⊆</mo> <mi>A</mi> <mo stretchy="false">(</mo> <mi>D</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> is at least <i>N</i>, then <i>D</i> contains a subdivision of <i>F</i> in which for every arc <i>e</i> of <i>F</i>, the corresponding branching path has <InlineEquation ID="IEq7"> <EquationSource Format="TEX">\(r_e\pmod {q_e}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>r</mi> <mi>e</mi> </msub> <mspace width="4.44443pt" /> <mrow> <mo stretchy="false">(</mo> <mo>mod</mo> <mspace width="0.277778em" /> <msub> <mi>q</mi> <mi>e</mi> </msub> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> many arcs of <i>Z</i>. We prove our result in a slightly more general setting, by considering, given a digraph <i>D</i> and two sets <InlineEquation ID="IEq8"> <EquationSource Format="TEX">\(Z_1\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>Z</mi> <mn>1</mn> </msub> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq9"> <EquationSource Format="TEX">\(Z_2\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>Z</mi> <mn>2</mn> </msub> </math></EquationSource> </InlineEquation> of arcs in <i>D</i>, the minimum number of parts in a vertex partition <InlineEquation ID="IEq10"> <EquationSource Format="TEX">\(\mathcal {P}\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">P</mi> </math></EquationSource> </InlineEquation> of&#xa0;<i>D</i> such that for every <InlineEquation ID="IEq11"> <EquationSource Format="TEX">\(X\in \mathcal {P}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>X</mi> <mo>∈</mo> <mi mathvariant="script">P</mi> </mrow> </math></EquationSource> </InlineEquation>, the subdigraph of&#xa0;<i>D</i> induced by <i>X</i> contains no directed cycle <i>C</i> with <InlineEquation ID="IEq12"> <EquationSource Format="TEX">\(|A(C)\cap Z_1|\ne |A(C)\cap Z_2|\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mrow> <mo stretchy="false">|</mo> <mi>A</mi> <mrow> <mo stretchy="false">(</mo> <mi>C</mi> <mo stretchy="false">)</mo> </mrow> <mo>∩</mo> </mrow> <msub> <mi>Z</mi> <mn>1</mn> </msub> <mrow> <mo stretchy="false">|</mo> <mo>≠</mo> <mo stretchy="false">|</mo> <mi>A</mi> <mrow> <mo stretchy="false">(</mo> <mi>C</mi> <mo stretchy="false">)</mo> </mrow> <mo>∩</mo> </mrow> <msub> <mi>Z</mi> <mn>2</mn> </msub> <mrow> <mo stretchy="false">|</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>. By setting <InlineEquation ID="IEq13"> <EquationSource Format="TEX">\((Z_1, Z_2)=(Z, \emptyset )\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mrow> <mo stretchy="false">(</mo> <msub> <mi>Z</mi> <mn>1</mn> </msub> <mo>,</mo> <msub> <mi>Z</mi> <mn>2</mn> </msub> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <mrow> <mo stretchy="false">(</mo> <mi>Z</mi> <mo>,</mo> <mi mathvariant="normal">∅</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> for <InlineEquation ID="IEq14"> <EquationSource Format="TEX">\(Z\subseteq A(D)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>Z</mi> <mo>⊆</mo> <mi>A</mi> <mo stretchy="false">(</mo> <mi>D</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>, we get an extension of the theorem of Steiner for directed cycles containing an arc of <i>Z</i>.</p>

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

On a Variant of Dichromatic Number for Digraphs with Prescribed Sets of Arcs

  • O-joung Kwon,
  • Xiaopan Lian

摘要

Steiner (JGT 2024) proved that given a digraph F and pairs of integers \((r_e, q_e)\) ( r e , q e ) with \(q_e\ge 2\) q e 2 for every arc e of F, there is an integer N such that every digraph of dichromatic number at least N contains a subdivision of F in which for every arc e of F, the corresponding branching path has length \(r_e\pmod {q_e}\) r e ( mod q e ) . We extend this result to directed cycles containing a specified set of arcs. We show that given such F and \(\{(r_e, q_e)\}_{e\in A(F)}\) { ( r e , q e ) } e A ( F ) , there is an integer N such that if the minimum number of parts in a vertex partition \(\mathcal {P}\) P of a digraph D such that each part has no directed cycles containing an arc of \(Z\subseteq A(D)\) Z A ( D ) is at least N, then D contains a subdivision of F in which for every arc e of F, the corresponding branching path has \(r_e\pmod {q_e}\) r e ( mod q e ) many arcs of Z. We prove our result in a slightly more general setting, by considering, given a digraph D and two sets \(Z_1\) Z 1 and \(Z_2\) Z 2 of arcs in D, the minimum number of parts in a vertex partition \(\mathcal {P}\) P of D such that for every \(X\in \mathcal {P}\) X P , the subdigraph of D induced by X contains no directed cycle C with \(|A(C)\cap Z_1|\ne |A(C)\cap Z_2|\) | A ( C ) Z 1 | | A ( C ) Z 2 | . By setting \((Z_1, Z_2)=(Z, \emptyset )\) ( Z 1 , Z 2 ) = ( Z , ) for \(Z\subseteq A(D)\) Z A ( D ) , we get an extension of the theorem of Steiner for directed cycles containing an arc of Z.