Scholarlink

<p>An equitable tree-<i>k</i>-coloring of a graph is a vertex coloring using <i>k</i> distinct colors such that every color class induces a forest and the sizes of any two color classes differ by at most one. The equitable vertex arboricity conjecture states that every graph with maximum degree <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2935_Article_IEq1.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="15" /> </InlineMediaObject> <EquationSource Format="TEX">\(\Delta \)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="normal">Δ</mi> </math></EquationSource> </InlineEquation> has an equitable tree-<i>m</i>-coloring for every <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2935_Article_IEq2.gif" Format="GIF" Height="23" Rendition="HTML" Resolution="72" Type="Linedraw" Width="85" /> </InlineMediaObject> <EquationSource Format="TEX">\(m\ge \lceil \frac{\Delta +1}{2} \rceil \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>m</mi> <mo>≥</mo> <mo>⌈</mo> <mfrac> <mrow> <mi mathvariant="normal">Δ</mi> <mo>+</mo> <mn>1</mn> </mrow> <mn>2</mn> </mfrac> <mo>⌉</mo> </mrow> </math></EquationSource> </InlineEquation>. In this paper, we verify this conjecture for graphs with maximum degree at most 6.</p>

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

Equitable Vertex Arboricity of Graphs with Low Maximum Degree

  • 期刊论文

  • 发表日期：

    2025年5月31日

查看全文
  • Ping Chen,
  • Weichan Liu,
  • Xin Zhang

摘要

An equitable tree-k-coloring of a graph is a vertex coloring using k distinct colors such that every color class induces a forest and the sizes of any two color classes differ by at most one. The equitable vertex arboricity conjecture states that every graph with maximum degree \(\Delta \) Δ has an equitable tree-m-coloring for every \(m\ge \lceil \frac{\Delta +1}{2} \rceil \) m ≥ ⌈ Δ + 1 2 ⌉ . In this paper, we verify this conjecture for graphs with maximum degree at most 6.