1-平面图的线性荫度
On the linear arboricity of 1-planar graphs
如果一个图可以画在平面上使得其中的每条边被其他边交叉最多一次,则称该图是1-平面图。如果一个森林的每个分支都是路,则称该森林为线性森林。一个图$G$的线性荫度$la(G)$是$G$可以边分解为线性森林的最小个数。关于图的线性荫度,Akiyama, Exoo与Harary猜想$lceil rac{Delta(G)}{2} ceilleq la(G)leq lceil rac{Delta(G)+1}{2} ceil$对每个图$G$都成立。本文证明了最大度$Deltageq 33$的1-平面图的线性荫度恰好为$lceilDelta/2 ceil$
graph is 1-planar if it can be drawn on a plane so that each edge is crossed by at most one other edge. A linear forest is a forest in which every connected component is a path. The linear arboricity $la(G)$ of a graph $G$ is the minimum number of linear forests in $G$, whose union is the set of all edges of $G$. Akiyama, Exoo and Harary conjectured that $lceil rac{Delta(G)}{2} ceilleq la(G)leq lceil rac{Delta(G)+1}{2} ceil$ for any graph $G$. In this paper, we prove that the linear arboricity of every 1-planar graph with maximum degree $Deltageq 33$ is exactly $lceilDelta/2 ceil$
吴建良、张欣、刘桂真
数学
1-平面图1-嵌入图线性荫度
1-planar graph 1-embedded graph linear arboricity
吴建良,张欣,刘桂真.1-平面图的线性荫度[EB/OL].(2012-02-10)[2025-08-02].http://www.paper.edu.cn/releasepaper/content/201202-228.点此复制
评论