In this paper we discuss a new edge-partition problem by introducing the triple arboricity of graphs. A triple arboricity, denoted ta(G), of a graph G is defined as the minimum number k such that the edge set of G can be decomposed into k subgraphs, each being a forest of maximum degree at most three. This concept can be thought of as a natural generalization of chromatic index and linear arboricity of a graph. We show that if G is a planar graph, then ta<InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1884_Article_IEq1.gif" Format="GIF" Height="23" Rendition="HTML" Resolution="72" Type="Linedraw" Width="96" /> </InlineMediaObject> <EquationSource Format="TEX">$(G)\le \lceil \frac{\Delta +1}{3}\rceil $</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> <mo>≤</mo> <mrow> <mo>⌈</mo> <mfrac> <mrow> <mi mathvariant="normal">Δ</mi> <mo>+</mo> <mn>1</mn> </mrow> <mn>3</mn> </mfrac> <mo>⌉</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> if <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1884_Article_IEq2.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="54" /> </InlineMediaObject> <EquationSource Format="TEX">$\Delta \ge 12$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="normal">Δ</mi> <mo>≥</mo> <mn>12</mn> </mrow> </math></EquationSource> </InlineEquation>, and moreover ta<InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1884_Article_IEq3.gif" Format="GIF" Height="23" Rendition="HTML" Resolution="72" Type="Linedraw" Width="80" /> </InlineMediaObject> <EquationSource Format="TEX">$(G)=\lceil \frac{\Delta }{3}\rceil $</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <mrow> <mo>⌈</mo> <mfrac> <mi mathvariant="normal">Δ</mi> <mn>3</mn> </mfrac> <mo>⌉</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> if <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1884_Article_IEq4.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="54" /> </InlineMediaObject> <EquationSource Format="TEX">$\Delta \ge 22$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="normal">Δ</mi> <mo>≥</mo> <mn>22</mn> </mrow> </math></EquationSource> </InlineEquation>. We also characterize the triple arboricity of <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1884_Article_IEq5.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="22" /> </InlineMediaObject> <EquationSource Format="TEX">$K_4$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>K</mi> <mn>4</mn> </msub> </math></EquationSource> </InlineEquation>-minor free graphs, i.e., every <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1884_Article_IEq5.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="22" /> </InlineMediaObject> <EquationSource Format="TEX">$K_4$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>K</mi> <mn>4</mn> </msub> </math></EquationSource> </InlineEquation>-minor free graph G with <InlineEquation ID="IEq7"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1884_Article_IEq7.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="46" /> </InlineMediaObject> <EquationSource Format="TEX">$\Delta \ge 4$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="normal">Δ</mi> <mo>≥</mo> <mn>4</mn> </mrow> </math></EquationSource> </InlineEquation> has ta<InlineEquation ID="IEq8"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1884_Article_IEq3.gif" Format="GIF" Height="23" Rendition="HTML" Resolution="72" Type="Linedraw" Width="80" /> </InlineMediaObject> <EquationSource Format="TEX">$(G)=\lceil \frac{\Delta }{3}\rceil $</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <mrow> <mo>⌈</mo> <mfrac> <mi mathvariant="normal">Δ</mi> <mn>3</mn> </mfrac> <mo>⌉</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>, and when <InlineEquation ID="IEq9"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1884_Article_IEq9.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="46" /> </InlineMediaObject> <EquationSource Format="TEX">$\Delta \le 3$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="normal">Δ</mi> <mo>≤</mo> <mn>3</mn> </mrow> </math></EquationSource> </InlineEquation>, we have ta<InlineEquation ID="IEq10"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1884_Article_IEq10.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="58" /> </InlineMediaObject> <EquationSource Format="TEX">$(G)\le 2$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> <mo>≤</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation>, and ta<InlineEquation ID="IEq11"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1884_Article_IEq11.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="57" /> </InlineMediaObject> <EquationSource Format="TEX">$(G)= 2$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation> if and only if G contains a cycle.

On the Triple Arboricity of Graphs

期刊论文
发表日期：

2025年5月22日

查看全文

Ning Song,
Yiqiao Wang,
Jianfeng Wang,
Weifan Wang

摘要

In this paper we discuss a new edge-partition problem by introducing the triple arboricity of graphs. A triple arboricity, denoted ta(G), of a graph G is defined as the minimum number k such that the edge set of G can be decomposed into k subgraphs, each being a forest of maximum degree at most three. This concept can be thought of as a natural generalization of chromatic index and linear arboricity of a graph. We show that if G is a planar graph, then ta $(G)\le \lceil \frac{\Delta +1}{3}\rceil $ $(G) \leq ⌈ \frac{Δ + 1}{3} ⌉$ if $\Delta \ge 12$ $Δ \geq 12$ , and moreover ta $(G)=\lceil \frac{\Delta }{3}\rceil $ $(G) = ⌈ \frac{Δ}{3} ⌉$ if $\Delta \ge 22$ $Δ \geq 22$ . We also characterize the triple arboricity of $K_4$ $K_{4}$ -minor free graphs, i.e., every $K_4$ $K_{4}$ -minor free graph G with $\Delta \ge 4$ $Δ \geq 4$ has ta $(G)=\lceil \frac{\Delta }{3}\rceil $ $(G) = ⌈ \frac{Δ}{3} ⌉$ , and when $\Delta \le 3$ $Δ \leq 3$ , we have ta $(G)\le 2$ $(G) \leq 2$ , and ta $(G)= 2$ $(G) = 2$ if and only if G contains a cycle.