The linear 2-arboricity of triangle free IC-planar graphs
-
摘要: 设G为最大度为Δ的IC-可平面图。图G的线性2-荫度la2(G)是将G分解为k个边不交森林的最小正整数k,其中森林的每个分支均为长至多为2的路。本文通过权转移方法研究了无三角形IC-可平面图的线性2-荫度,得到la2(G)≤$\left\lceil{\frac{{\mathit{\Delta}+1}}{2}}\right\rceil$+5。Abstract: Let G be an IC-planar graph with maximum degree Δ. The linear 2-arboricity la2(G) of a graph G, is the smallest k such that G can be partitioned into k edge-disjoint forests, whose components are paths of length at most 2. This paper, we study the linear 2-arboricity of triangle free IC-planar graphs by the discharging method and get that la2(G) ≤ $\left\lceil {\frac{{\mathit{\Delta} + 1}}{2}} \right\rceil $+ 5.
-
Keywords:
- IC-planar graph /
- linear 2-arboricity /
- discharging method
-
0. 引言
文中出现的图均为有限无向简单图。设$ G $为最大度为$ \mathit\Delta $的IC-可平面图,图$ G $的顶点集、边集、最大度和最小度分别用$ V\left(G\right)、$ $ E\left(G\right)、\mathit\Delta $和$ \delta $表示。用$ g $表示图$ G $的最短圈的长度。对任意$ v\in V\left(G\right), $用$ {d}_{G}\left(v\right) $表示$ v $在$ G $中的度。分别称满足$ {d}_{G}\left(v\right)=i $和$ {d}_{G}\left(v\right)\ge i $的点为$ i $-点和$ {i}^{+} $-点。称1-点为叶子点。若$ uv\in E\left(G\right) $且$ {d}_{G}\left(u\right)+{d}_{G}\left(v\right)\le l, $则称$ uv $为$ G $的$ l $-轻边。若偶圈$ C={v}_{0}{v}_{1}\cdots {v}_{2m-1}{v}_{0}, $ $ m\ge 2, $满足对任意$ i\in \left\{0, 2, \cdots , 2m-2\right\} $都有$ {d}_{G}\left({v}_{i}\right)=2, $则称$ C $为2-交替圈。图$ G $的边划分是指将图$ G $分解为子图$ {G}_{1},{G}_{2},\cdots ,{G}_{t}, $使得$ E\left(G\right)=E\left({G}_{1}\right)\bigcup E\left({G}_{2}\right)\bigcup \cdots \bigcup E\left({G}_{t}\right), $且对任意$ 1\le i < j\le t $都有$ E\left({G}_{i}\right)\bigcap E\left({G}_{j}\right)=\mathrm{\varnothing }。 $若图$ G $满足$ \delta \le 1 $或$ G $有一条$ \left(h+6\right) $-轻边或$ G $有一个2-交替圈,则称$ G $具有$ {L}_{h} $-性质,其中$ h\ge 1。 $若图$ G $的每个子图都具有$ {L}_{h} $-性质,则称$ G $具有$ {L}_{h} $-遗传性。用$ {\mathscr{L}}_{h} $表示所有具有$ {L}_{h} $-遗传性的图的集合。
若图$ G $可以嵌入在平面上,使其任意2条边仅在端点处才可能相交,则称$ G $为可平面图。称可平面图$ G $的上述平面嵌入为平面图,仍用$ G $表示。用$ F\left(G\right) $表示平面图$ G $的面集。对任意$ f\in F\left(G\right), $称面$ f $的边界途径的长为$ f $的度,用$ d\left(f\right) $表示。分别称满足$ d\left(f\right)=i $和$ d\left(f\right)\ge i $的面为$ i $-面和$ {i}^{+} $-面。若图$ G $可以嵌入在平面上,使得每条边至多被交叉一次,则称$ G $为1-可平面图。将1-可平面图满足该条件的平面嵌入称为1-平面图。若$ G $为1-可平面图且$ G $的每个顶点至多与一个交叉点相邻,则称$ G $为IC-可平面图。将IC-可平面图满足该条件的平面嵌入称为IC-平面图。显然,IC-可平面图是可平面图的扩展,是1-可平面图的子类。1-平面图$ G $的关联平面图是指将$ G $的所有交叉点都视为新4-点而得到的平面图,用$ {G}^{\times } $表示。在图$ {G}^{\times } $中,称新4-点为假点,称与假点关联的面为假面。
线性$ m $-森林为每个连通分支皆为长至多为$ m $的路的图。Habib和Péroche [1]首次引入了线性$ m $-荫度的概念,图$ G $的线性$ m $-荫度$ \mathrm{l}{\mathrm{a}}_{m}\left(G\right) $是指将$ G $边划分成的线性$ m $-森林的最少数目,特别地,$ \mathrm{l}{\mathrm{a}}_{\mathrm{\infty }}\left(G\right) $表示每个分支路长度没有限制的情况,即为图的线性荫度$ \mathrm{l}\mathrm{a}\left(G\right) $;Akiyama等[2]提出了著名的线性荫度猜想, 即对于任意图$ G $有$ ⌈\frac{\mathit\Delta }{2}⌉\le \mathrm{l}\mathrm{a}\left(G\right)\le ⌈\frac{\mathit\Delta +1}{2}⌉ $;最近,Chen等[3]得到对于$ \mathit\Delta \ge 2{k}^{2}-k $的$ k $-退化图$ G $有$ \mathrm{l}\mathrm{a}\left(G\right)=⌈\frac{\mathit\Delta }{2}⌉ $。文献[4-10]给出了近几年线性$ m $-荫度的相关研究结果。2003年,Lih等[11]研究了可平面图的线性2-荫度,得到一般可平面图线性2-荫度的上界为$ ⌈\frac{\mathit\Delta +1}{2}⌉+12, $无三角形可平面图线性2-荫度的上界为$ ⌈\frac{\mathit\Delta +1}{2}⌉+6, $同时也得到了$ g\ge 5 $和$ g\ge 7 $的可平面图线性2-荫度的上界;2017年,Wang等[12]将一般可平面图线性2-荫度的上界改进为$ ⌈\frac{\mathit\Delta +1}{2}⌉+6。 $文献[13-17]给出了一些圈限制条件下可平面图线性2-荫度的相关结果。2019年,Liu等[18]研究了1-可平面图的线性2-荫度,得到其上界为$ ⌈\frac{\mathit\Delta +1}{2}⌉+14 $;2021年,Liu等[19]将此结果改进为$ ⌈\frac{\mathit\Delta +1}{2}⌉+7 $;随后,Zhang和Liu[20]研究了圈限制条件下1-可平面图的线性2-荫度,得到无三角形1-可平面图线性2-荫度的上界为$ ⌈\frac{\mathit\Delta +1}{2}⌉+6 $;张露[21]给出了不含4-圈和$ g\ge 6 $的相关结果。本文研究了无三角形IC-可平面图的线性2-荫度,得到如下定理。
定理 若$ G $为无三角形IC-可平面图,则$ \mathrm{l}{\mathrm{a}}_{2}\left(G\right)\le ⌈\frac{\mathit\Delta +1}{2}⌉+5。 $
1. 相关引理
引理1[22] 若$ G\in {\mathscr{L}}_{h}, $则$ G $可以边划分为2个森林$ {F}_{1}、$ $ {F}_{2} $和1个子图$ H, $使得对于每个$ v\in V\left(G\right), $都有$ {d}_{H}\left(v\right)\le h+1, $ $ {d}_{{F}_{i}}\left(v\right)\le \mathrm{m}\mathrm{a}\mathrm{x}\left\{2, ⌈\frac{{d}_{G}\left(v\right)-h}{2}⌉\right\}, $ $ i=1,2。 $
引理2[23] 若$ G $为任意图,则$ \mathrm{l}{\mathrm{a}}_{2}\left(G\right)\le \mathit\Delta 。 $
引理3[24] 若$ G $为森林,则$ \mathrm{l}{\mathrm{a}}_{2}\left(G\right)\le ⌈\frac{\mathit\Delta +1}{2}⌉。 $
引理4[11] 若$ G $可以边划分为子图$ {G}_{1},{G}_{2},\cdots , $ $ {G}_{t}, $则$ \mathrm{l}{\mathrm{a}}_{2}\left(G\right)\le \sum\limits _{i=1}^{t}\mathrm{l}{\mathrm{a}}_{2}\left({G}_{i}\right) $。
引理5 若$ G $为$ \delta \ge 2 $的无三角形IC-可平面图,则$ G $有1条11-轻边或有1个2-交替圈。
证明 利用反证法。设$ G $是引理5的反例,则$ G $无11-轻边且无2-交替圈。选取$ G $的一个交叉点数最少的IC-平面图仍记为$ G。 $不妨设$ G $是连通的,用$ {G}_{2} $表示由$ G $中所有与2-点关联的边生成的边导出子图。由于$ G $的任意2个2-点都不相邻,故$ {G}_{2} $无奇圈;又因为$ G $无2-交替圈,所以$ {G}_{2} $无偶圈。因此$ {G}_{2} $为森林。注意到$ {G}_{2} $的叶子点不为$ G $的2-点,由归纳法易知$ {G}_{2} $存在1个包含$ G $的所有2-点的匹配$ M。 $如果$ uv\in E\left(M\right) $且$ {d}_{G}\left(v\right)=2, $那么称$ u $为$ v $的父亲点,在$ G $中与$ v $相邻的另一个点称为$ v $的母亲点。注意到图$ G $的2-点有且仅有1个父亲点,每个$ {10}^{+} $-点至多为1个2-点的父亲点。
由$ G $无三角形且交叉点数最少知2-点在$ {G}^{\times } $中不与3-面关联。故2-点在$ {G}^{\times } $中或与1个$ {5}^{+} $-面关联,或与2个4-面关联。称在$ {G}^{\times } $中与2个4-面关联的2-点为特殊2-点,其他2-点称为非特殊2-点。称特殊2-点所在面上的且不与其相邻的点为其对应点,注意到特殊2-点有2个对应点。
对任意$ f\in F\left({G}^{\times }\right) $,用$ {t}_{2}\left(f\right) $表示与面$ f $关联的2-点的个数。对任意$ v\in V\left(G\right), $用$ {s}_{2}^{\mathrm{*}}\left(v\right) $表示在$ G $中与$ v $相邻的特殊2-点的个数。用$ {p}_{3}\left(v\right) $表示与$ v $关联的假3-面的个数。在$ {G}^{\times } $中,将$ {d}_{{G}^{\times }}\left(v\right) $简记为$ d\left(v\right) $。
对任意$ uv\in E\left(G\right), $有$ {d}_{G}\left(u\right)+{d}_{G}\left(v\right)\ge 12, $故有事实1成立。
事实1 图$ G $中2-点与$ {10}^{+} $-点相邻,3-点与$ {9}^{+} $-点相邻。
由事实1知,与面$ f $关联的任意2个2-点都不相邻,故有事实2成立。
事实2 对于$ {G}^{\times } $的每个面$ f $,都有$ {t}_{2}\left(f\right)\le ⌊\frac{d\left(f\right)}{2}⌋。 $
由IC-平面图的定义和$ G $无三角形知事实3成立。
事实3 对任意$ v\in V\left(G\right), $都有$ {p}_{3}\left(v\right)\le 1。 $
断言1 特殊2-点不与假点相邻且至少与1个真4-面关联,所在真4-面上的对应点为$ {3}^{+} $-点。
证明 设$ v $为特殊2-点,不妨记与$ v $关联的2个4-面分别为$ {f}_{1} $和$ {f}_{2}。 $若$ v $与假点相邻,则$ {f}_{1} $和$ {f}_{2} $均为假4-面,可得$ G $的1个3-圈,与$ G $无三角形矛盾,故$ v $不与假点相邻。注意到$ v $不与假点相邻,若$ {f}_{1} $和$ {f}_{2} $均为假4-面,则$ v $的2个邻点都与2个交叉点相邻,与$ G $为IC-平面图矛盾。因此$ {f}_{1} $和$ {f}_{2} $不同时为假4-面。由于$ G $无2-交替圈,故$ v $在真4-面上的对应点为$ {3}^{+} $-点。
若$ uv,xy\in E\left(G\right), $且$ uv,xy $相交于点$ z, $则在$ {G}^{\times } $中称$ u $和$ v $($ x $和$ y $)互为次邻点。
断言2 对$ {G}^{\times } $的每个$ k $-点$ v $($ k\ge 10 $),都有$ {s}_{2}^{\mathrm{*}}\left(v\right)+{p}_{3}\left(v\right)\le ⌈\frac{k}{2}⌉。 $
证明 不妨设$ v $在$ G $中的邻点按顺时针方向依次为$ {v}_{1},{v}_{2},\cdots ,{v}_{k}。 $由$ G $为IC-平面图知$ v $至多与1个假点相邻,故分2种情形。
情形1:如果$ v $不与假点相邻,那么$ {p}_{3}\left(v\right)=0。 $若存在$ {i}_{0}\in \left\{1, 2, \cdots , k\right\}, $ $ {v}_{{i}_{0}} $为特殊2-点,则结合断言1知$ {v}_{{i}_{0}-1},{v}_{{i}_{0}+1} $均为$ {3}^{+} $-点(这里分别将$ {v}_{0},{v}_{k+1} $视为$ {v}_{k},{v}_{1} $)。故$ {s}_{2}^{\mathrm{*}}\left(v\right)\le ⌈\frac{k}{2}⌉, $因此,$ {s}_{2}^{\mathrm{*}}\left(v\right)+{p}_{3}\left(v\right)\le ⌈\frac{k}{2}⌉+0=⌈\frac{k}{2}⌉。 $
情形2:如果$ v $与假点相邻,那么由断言1知$ v $的次邻点不为特殊2-点。由事实3知$ {p}_{3}\left(v\right)\le 1。 $若$ {p}_{3}\left(v\right)=0, $结合$ v $的次邻点不为特殊2-点和情形1的讨论知$ {s}_{2}^{\mathrm{*}}\left(v\right)\le ⌈\frac{k}{2}⌉ $;若$ {p}_{3}\left(v\right)=1, $由$ G $的交叉点数最少知2-点不与假3-面关联,又由$ v $的次邻点不为特殊2-点,故结合情形1讨论知$ {s}_{2}^{\mathrm{*}}\left(v\right)\le ⌈\frac{k}{2}⌉-1。 $因此$ {s}_{2}^{\mathrm{*}}\left(v\right)+{p}_{3}\left(v\right)\le ⌈\frac{k}{2}⌉。 $
对任意$ v\in V\left({G}^{\times }\right), $ $ f\in F\left({G}^{\times }\right), $分别定义初始权$ \omega \left(v\right)=d\left(v\right)-4, $ $ \omega \left(f\right)=d\left(f\right)-4。 $由欧拉公式可知,
$$ \begin{array}{c}\sum\limits _{v\in V\left({G}^{\times }\right)}\omega \left(v\right)+\sum\limits _{f\in F\left({G}^{\times }\right)}\omega \left(f\right)=\\ \sum\limits _{v\in V\left({G}^{\times }\right)}\left(d\left(v\right)-4\right)+\sum\limits _{f\in F\left({G}^{\times }\right)}\left(d\left(f\right)-4\right)=-8。\end{array} $$ (1) 利用如下权转移规则,重新分配$ {G}^{\times } $中顶点与面的权:
R1:若$ f $为$ {5}^{+} $-面,则$ f $给每个与其关联的2-点转移权$ \frac{1}{2}。 $
R2:若$ v $为$ {5}^{+} $-点,则$ v $给每个与其关联的假3-面转移权1。
R3:若$ v $为$ {9}^{+} $-点,则$ v $给在$ G $中每个与其相邻的3-点转移权$ \frac{1}{3}。 $
R4:若$ v $为$ {10}^{+} $-点,则$ v $给在$ G $中每个与其相邻的2-点转移权情况如下:
R4.1:对于与$ v $相邻的特殊2-点$ u, $若$ v $为$ u $的父亲点,则$ v $给$ u $转移权$ \frac{3}{2} $;若$ v $为$ u $的母亲点,则$ v $给$ u $转移权$ \frac{1}{2}。 $
R4.2:对于与$ v $相邻的非特殊2-点$ u, $若$ v $为$ u $的父亲点,则$ v $给$ u $转移权$ \frac{7}{6} $;若$ v $为$ u $的母亲点,则$ v $给$ u $转移权$ \frac{1}{3}。 $
用$ \tilde{\omega }\left(v\right) $与$ \tilde{\omega }\left(f\right) $分别表示权转移结束后顶点$ v $与面$ f $的新权值。注意到在权转移过程中总权和始终保持不变,若证得对任意$ v\in V\left({G}^{\times }\right) $和$ f\in F\left({G}^{\times }\right) $都有$ \tilde{\omega }\left(v\right)\ge 0 $且$ \tilde{\omega }\left(f\right)\ge 0, $则与式$ \left(1\right) $矛盾,从而引理5得证。下面考虑$ {G}^{\times } $的每个顶点和每个面的新权值。
首先考虑$ {G}^{\times } $中每个面的新权值:
$ \left(1\right) $ $ d\left(f\right)=3。 $由$ G $无三角形知$ {G}^{\times } $的3-面皆为假3-面。由于对任意$ uv\in E\left(G\right), $均有$ {d}_{G}\left(u\right)+{d}_{G}\left(v\right)\ge 12, $因此$ f $至少与一个$ {5}^{+} $-点关联。故由R2可得,$ \tilde{\omega }\left(f\right)\ge 3-4+1=0。 $
$ \left(2\right) $ $ d\left(f\right)=4。 $此时$ \tilde{\omega }\left(f\right)=\omega \left(f\right)=d\left(f\right)-4=0。 $
$ \left(3\right) $ $ d\left(f\right)\ge 5。 $由事实2知$ {t}_{2}\left(f\right)\le ⌊\frac{d\left(f\right)}{2}⌋。 $故由R1可得
$$ \begin{array}{c}\tilde{\omega }\left(f\right)=\omega \left(f\right)-\frac{1}{2}{t}_{2}\left(f\right)\ge \\ ⌈\frac{d\left(f\right)}{2}⌉+\frac{1}{2}⌊\frac{d\left(f\right)}{2}⌋-4\ge 0。\end{array} $$ 再考虑$ {G}^{\times } $中每个顶点的新权值。
$ \left(4\right) $ $ d\left(v\right)=2。 $由事实1知,在$ G $中与$ v $相邻的2个顶点均为$ {10}^{+} $-点,且其中1个$ {10}^{+} $-点为$ v $的父亲点。此时有以下2种情况:
① 若$ v $为特殊2-点,则由R4.1可得$ \tilde{\omega }\left(v\right)=2-4+\frac{3}{2}+\frac{1}{2}=0。 $
② 若$ v $为非特殊2-点,则$ v $至少与1个$ {5}^{+} $-面关联。故由R1和R4.2可得
$$ \tilde{\omega }\left(v\right)=2-4+\frac{1}{2}+\frac{7}{6}+\frac{1}{3}=0。 $$ $ \left(5\right) $ $ d\left(v\right)=3。 $由事实1知,在$ G $中与$ v $相邻的3个顶点均为$ {9}^{+} $-点。故由R3可得
$$ \tilde{\omega }\left(v\right)=3-4+\frac{1}{3}\times 3=0。 $$ $ \left(6\right) $ $ d\left(v\right)=4。 $此时$ \tilde{\omega }\left(v\right)=\omega \left(v\right)=d\left(v\right)-4=0。 $
$ \left(7\right) $ $ 5\le d\left(v\right)\le 8。 $由事实3知$ {p}_{3}\left(v\right)\le 1, $故由R2可得$ \tilde{\omega }\left(v\right)=\omega \left(v\right)-{p}_{3}\left(v\right)\ge d\left(v\right)-4-1\ge 0。 $
$ \left(8\right) $ $ d\left(v\right)=9。 $由事实3知$ {p}_{3}\left(v\right)\le 1, $故由R2和R3可得$ \tilde{\omega }\left(v\right)\ge 9-4-1-\frac{1}{3}\times 9 > 0。 $
$ \left(9\right) $ $ d\left(v\right)\ge 10。 $由事实3知$ {p}_{3}\left(v\right)\le 1。 $若$ v $在$ G $中不与2-点相邻,则由R2和R3可得
$$ \begin{array}{c}\tilde{\omega }\left(v\right)=\omega \left(v\right)-{p}_{3}\left(v\right)-\frac{1}{3}d\left(v\right)\ge \\ d\left(v\right)-4-1-\frac{1}{3}d\left(v\right)=\frac{2}{3}d\left(v\right)-5 > 0。\end{array} $$ 下面考虑$ v $在$ G $中与2-点相邻的情况。由断言2知$ {s}_{2}^{\mathrm{*}}\left(v\right)+{p}_{3}\left(v\right)\le ⌈\frac{k}{2}⌉。 $注意到$ v $至多为1个2-点的父亲点。
若$ v $不为任意2-点的父亲点,则由R2-R4可得
$$ \begin{array}{c}\tilde{\omega }\left(v\right)=\omega \left(v\right)-{p}_{3}\left(v\right)-\frac{1}{2}{s}_{2}^{\mathrm{*}}\left(v\right)-\frac{1}{3}\left(d\left(v\right)-{s}_{2}^{\mathrm{*}}\left(v\right)\right)\ge \\ d\left(v\right)-4-1-\frac{1}{2}\times \left(⌈\frac{d\left(v\right)}{2}⌉-1\right)-\frac{1}{3}\times \left(⌊\frac{d\left(v\right)}{2}⌋+1\right)=\\ \frac{2}{3}⌊\frac{d\left(v\right)}{2}⌋+\frac{1}{2}⌈\frac{d\left(v\right)}{2}⌉-\frac{29}{6} > 0。\end{array} $$ 若$ v $为某个2-点的父亲点,不妨记该2-点为$ u。 $此时有以下2种情况:
① 若$ u $为非特殊2-点,则由R2~R4可得
$$ \begin{array}{c}\tilde{\omega }\left(v\right)=\omega \left(v\right)-{p}_{3}\left(v\right)-\frac{7}{6}-\frac{1}{2}{s}_{2}^{\mathrm{*}}\left(v\right)-\frac{1}{3}\left(d\right(v)-{s}_{2}^{\mathrm{*}}(v)-1)\ge \\ d\left(v\right)-4-1-\frac{7}{6}-\frac{1}{2}\times \left(⌈\frac{d\left(v\right)}{2}⌉-1\right)-\frac{1}{3}\times ⌊\frac{d\left(v\right)}{2}⌋=\\ \frac{2}{3}⌊\frac{d\left(v\right)}{2}⌋+\frac{1}{2}⌈\frac{d\left(v\right)}{2}⌉-\frac{17}{3} > 0;\end{array} $$ ② 若$ u $为特殊2-点,则由R2~R4可得
$$ \tilde{\omega }\left(v\right)=\omega \left(v\right)-{p}_{3}\left(v\right)-\frac{3}{2}-\frac{1}{2}\left({s}_{2}^{\mathrm{*}}\right(v)-1)-\frac{1}{3}\left(d\right(v)-{s}_{2}^{\mathrm{*}}(v\left)\right)\ge \\ d\left(v\right)-4-1-\frac{3}{2}-\frac{1}{2}\times \left(⌈\frac{d\left(v\right)}{2}⌉-1-1\right)-\frac{1}{3}\times \left(⌊\frac{d\left(v\right)}{2}⌋+1\right)=\\ \frac{2}{3}⌊\frac{d\left(v\right)}{2}⌋+\frac{1}{2}⌈\frac{d\left(v\right)}{2}⌉-\frac{35}{6}\ge 0。 $$ 综上,对任意$ v\in V\left({G}^{\times }\right) $和$ f\in F\left({G}^{\times }\right), $都有$ \tilde{\omega }\left(v\right)\ge 0 $且$ \tilde{\omega }\left(f\right)\ge 0, $矛盾。引理5证毕。
下面证明本文的主要结论。
2. 定理的证明
若$ \mathit\Delta \le 7, $则由引理2知$ \mathrm{l}{\mathrm{a}}_{2}\left(G\right)\le \mathit\Delta \le ⌈\frac{\mathit\Delta +1}{2}⌉+5。 $若$ \mathit\Delta \ge 8, $则由引理1和引理5知$ G $可以边划分为2个森林$ {F}_{1}、{F}_{2} $和一个子图$ H, $其中对于$ i=1,2, $ $ \mathit\Delta \left({F}_{i}\right)\le ⌈\frac{\mathit\Delta -5}{2}⌉,\mathit\Delta \left(H\right)\le 6。 $故由引理2~4知,
$$ \begin{array}{c}\mathrm{l}{\mathrm{a}}_{2}\left(G\right)\le \mathrm{l}{\mathrm{a}}_{2}\left({F}_{1}\right)+\mathrm{l}{\mathrm{a}}_{2}\left({F}_{2}\right)+\mathrm{l}{\mathrm{a}}_{2}\left(H\right)\le \\ ⌈\frac{⌈\frac{\mathit\Delta -5}{2}⌉+1}{2}⌉+⌈\frac{⌈\frac{\mathit\Delta -5}{2}⌉+1}{2}⌉+6\le ⌈\frac{\mathit\Delta +1}{2}⌉+5。\end{array} $$ 综上所述,定理得证。
-
[1] HABIB M, PÉROCHE P. Some problems about linear arboricity[J]. Discrete Mathematics, 1982, 41(2): 219-220. doi: 10.1016/0012-365X(82)90209-6 [2] AKIYAMA J, EXOO G, HARARY F. Covering and packing in graphs Ⅲ: cyclic and acyclic invariants[J]. Mathematica Slovaca, 1980, 30: 405-417. [3] CHEN G T, HAO Y L, YU G N. Linear arboricity of degenerate graphs[J/OL]. [2022-03-01]. arXiv: 2207.07169,2022. [4] HE S J, HAO R X, ZUO L C. The linear (n-1)-arboricity of some lexicographic product graphs[J]. Applied Mathematics and Computation, 2018, 338: 152-163. doi: 10.1016/j.amc.2018.06.007 [5] HUANG T F, ZUO L C, SHANG C H. The linear karboricity of cartesian product of multipartite balanced complete graphs[J]. IAENG International Journal of Applied Mathematics, 2018, 48(3): 362-367. [6] JIA N, MAO Y P, WANG Z, et al. Linear k-arboricity of caylay graphs on abelian groups with given degree[J]. Mathematics in Computer Science, 2021, 15(4): 743-755. doi: 10.1007/s11786-021-00503-6 [7] ZHOU X L, YANG C, HE W H. The linear k-arboricity of symmetric directed trees[J]. AIMS Mathematics, 2022, 7(2): 1603-1614. doi: 10.3934/math.2022093 [8] LI Y C, HU X X. The linear 2-arboricity of sparse graphs[J]. Discrete Mathematics, Algorithms and Applications, 2017, 9(4): 1750047. doi: 10.1142/S1793830917500471 [9] JIN X, XU C Q. The linear 2-arboricity of graphs with mad(G) ≤ 10/3[J]. Utilitas Mathematica, 2018, 106: 315-318. [10] HU X X, KONG J X, WANG Y Q. Linear 2-arboricity of planar graphs with maximum degree nine[J]. Journal of Applied Analysis and Computation, 2021, 11(4): 2193-2210. [11] LIH K W, TONG L D, WANG W F. The linear 2-arboricity of planar graphs[J]. Graphs and Combinatorics, 2003, 19(2): 241-248. doi: 10.1007/s00373-002-0504-x [12] WANG Y Q, HU X X, WANG W F. A note on the linear 2-arboricity of planar graphs[J]. Discrete Mathematics, 2017, 340(7): 1449-1455. doi: 10.1016/j.disc.2017.01.027 [13] MA Q, WU J L, YU X. Planar graphs without 5-cycles or without 6-cycles[J]. Discrete Mathematics, 2009, 309(10): 2998-3005. doi: 10.1016/j.disc.2008.07.033 [14] NIU H X, CAI J S. Linear 2-arboricity of planar graphs with neither 3-cycles nor adjacent 4-cycles[J]. Graphs and Combinatorics, 2013, 29(3): 661-667. doi: 10.1007/s00373-011-1122-2 [15] WANG Y Q. On the linear 2-arboricity of planar graph without normally adjacent 3-cycles and 4-cycles[J]. International Journal of Computer Mathematics, 2017, 94(5): 981-988. doi: 10.1080/00207160.2016.1158813 [16] CHEN H Y, TAN X, WU J L. The linear 2-arboricity of planar graphs without adjacent short cycles[J]. Bulletin of the Korean Mathematical Society, 2012, 49(1): 145-154. doi: 10.4134/BKMS.2012.49.1.145 [17] XU C Q, ZHAO Z Z, YAO M. On the linear 2-arboricity of planar graphs without intersecting 3-cycles or intersecting 4-cycles[J]. Ars Combinatoria, 2018, 136: 383-389. [18] LIU J, HU X X, WANG W F, et al. Light structures in 1-planar graphs with an application to linear 2-arboricity[J]. Discrete Applied Mathematics, 2019, 267: 120-130. doi: 10.1016/j.dam.2019.05.001 [19] LIU J, WANG Y Q, WANG P, et al. An improved upper bound on the linear 2-arboricity of 1-planar graphs[J]. Acta Mathematica Sinica, English Series, 2021, 37(2): 262-278. doi: 10.1007/s10114-020-9488-9 [20] ZHANG L, LIU J. The linear 2-arboricity of 1-planar graphs without 3-cycles[J]. Discrete Mathematics, Algorithms and Applications, 2021, 13(6): 2150078. [21] 张露. 1-平面图的线性2-荫度[D]. 金华: 浙江师范大学, 2021. [22] WANG W F, LI Y C, HU X X, et al. Linear 2-arboricity of toroidal graphs[J]. Bulletin of the Malaysian Mathematical Sciences Society, 2018, 41(4): 1907-1921. [23] BERMOND J C, FOUQUET J L, HABIB M, et al. On linear k-arboricity[J]. Discrete Mathematics, 1984, 52(2-3): 123-132. [24] CHEN B L, FU H L, HUANG K C. Decomposing graphs into forests of paths with size less than three[J]. The Aus-tralasian Journal of Combinatorics, 1991, 3: 55-73.