<p>The DP color function <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(P_{DP}({\mathcal {H}},k)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>P</mi> <mrow> <mi mathvariant="italic">DP</mi> </mrow> </msub> <mrow> <mo stretchy="false">(</mo> <mi mathvariant="script">H</mi> <mo>,</mo> <mi>k</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> of a hypergraph <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\({\mathcal {H}}\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">H</mi> </math></EquationSource> </InlineEquation> for <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(k\in \mathbb N\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>k</mi> <mo>∈</mo> <mi mathvariant="double-struck">N</mi> </mrow> </math></EquationSource> </InlineEquation> is introduced, based on the DP coloring introduced by Bernshteyn and Kostochka, which is the minimum value of <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(P_{DP}(\mathcal {H},\mathcal {F})\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>P</mi> <mrow> <mi mathvariant="italic">DP</mi> </mrow> </msub> <mrow> <mo stretchy="false">(</mo> <mi mathvariant="script">H</mi> <mo>,</mo> <mi mathvariant="script">F</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> over all <i>k</i>-fold covers <InlineEquation ID="IEq5"> <EquationSource Format="TEX">\(\mathcal {F}\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">F</mi> </math></EquationSource> </InlineEquation> of <InlineEquation ID="IEq6"> <EquationSource Format="TEX">\(\mathcal {H}\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">H</mi> </math></EquationSource> </InlineEquation>. It is an extension of the chromatic polynomial of <InlineEquation ID="IEq7"> <EquationSource Format="TEX">\({\mathcal {H}}\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">H</mi> </math></EquationSource> </InlineEquation> with the property that <InlineEquation ID="IEq8"> <EquationSource Format="TEX">\(P_{DP}({\mathcal {H}},k)\le P({\mathcal {H}},k)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>P</mi> <mrow> <mi mathvariant="italic">DP</mi> </mrow> </msub> <mrow> <mo stretchy="false">(</mo> <mi mathvariant="script">H</mi> <mo>,</mo> <mi>k</mi> <mo stretchy="false">)</mo> </mrow> <mo>≤</mo> <mi>P</mi> <mrow> <mo stretchy="false">(</mo> <mi mathvariant="script">H</mi> <mo>,</mo> <mi>k</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> for all positive integers <i>k</i>. In this article, we obtain an upper bound for <InlineEquation ID="IEq9"> <EquationSource Format="TEX">\(P_{DP}({\mathcal {H}},k)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>P</mi> <mrow> <mi mathvariant="italic">DP</mi> </mrow> </msub> <mrow> <mo stretchy="false">(</mo> <mi mathvariant="script">H</mi> <mo>,</mo> <mi>k</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> when <InlineEquation ID="IEq10"> <EquationSource Format="TEX">\({\mathcal {H}}\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">H</mi> </math></EquationSource> </InlineEquation> is a connected <i>r</i>-uniform hypergraph for <InlineEquation ID="IEq11"> <EquationSource Format="TEX">\(r\ge 2\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>r</mi> <mo>≥</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation>, and the upper bound is attained if and only if <InlineEquation ID="IEq12"> <EquationSource Format="TEX">\({\mathcal {H}}\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">H</mi> </math></EquationSource> </InlineEquation> is an <i>r</i>-uniform hypertree. We also show that <InlineEquation ID="IEq13"> <EquationSource Format="TEX">\(P_{DP}({\mathcal {H}},k)= P({\mathcal {H}},k)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>P</mi> <mrow> <mi mathvariant="italic">DP</mi> </mrow> </msub> <mrow> <mo stretchy="false">(</mo> <mi mathvariant="script">H</mi> <mo>,</mo> <mi>k</mi> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <mi>P</mi> <mrow> <mo stretchy="false">(</mo> <mi mathvariant="script">H</mi> <mo>,</mo> <mi>k</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> holds when <InlineEquation ID="IEq14"> <EquationSource Format="TEX">\({\mathcal {H}}\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">H</mi> </math></EquationSource> </InlineEquation> is an <i>r</i>-uniform hypertree or a unicyclic linear <i>r</i>-uniform hypergraph with an odd cycle for <InlineEquation ID="IEq15"> <EquationSource Format="TEX">\(r\ge 3\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>r</mi> <mo>≥</mo> <mn>3</mn> </mrow> </math></EquationSource> </InlineEquation>. These conclusions coincide with the known results of graphs.</p>

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

DP color functions of hypergraphs

  • Ruiyi Cui,
  • Liangxia Wan,
  • Fengming Dong

摘要

The DP color function \(P_{DP}({\mathcal {H}},k)\) P DP ( H , k ) of a hypergraph \({\mathcal {H}}\) H for \(k\in \mathbb N\) k N is introduced, based on the DP coloring introduced by Bernshteyn and Kostochka, which is the minimum value of \(P_{DP}(\mathcal {H},\mathcal {F})\) P DP ( H , F ) over all k-fold covers \(\mathcal {F}\) F of \(\mathcal {H}\) H . It is an extension of the chromatic polynomial of \({\mathcal {H}}\) H with the property that \(P_{DP}({\mathcal {H}},k)\le P({\mathcal {H}},k)\) P DP ( H , k ) P ( H , k ) for all positive integers k. In this article, we obtain an upper bound for \(P_{DP}({\mathcal {H}},k)\) P DP ( H , k ) when \({\mathcal {H}}\) H is a connected r-uniform hypergraph for \(r\ge 2\) r 2 , and the upper bound is attained if and only if \({\mathcal {H}}\) H is an r-uniform hypertree. We also show that \(P_{DP}({\mathcal {H}},k)= P({\mathcal {H}},k)\) P DP ( H , k ) = P ( H , k ) holds when \({\mathcal {H}}\) H is an r-uniform hypertree or a unicyclic linear r-uniform hypergraph with an odd cycle for \(r\ge 3\) r 3 . These conclusions coincide with the known results of graphs.