On the linear arboricity of 1-planar graphs
首发时间:2012-02-10
Abstract:A 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 $lceilrac{Delta(G)}{2} ceilleq la(G)leq lceilrac{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$
keywords: 1-planar graph, 1-embedded graph, linear arboricity
点击查看论文中文信息
1-平面图的线性荫度
摘要:如果一个图可以画在平面上使得其中的每条边被其他边交叉最多一次,则称该图是1-平面图。如果一个森林的每个分支都是路,则称该森林为线性森林。一个图$G$的线性荫度$la(G)$是$G$可以边分解为线性森林的最小个数。关于图的线性荫度,Akiyama, Exoo与Harary猜想$lceilrac{Delta(G)}{2} ceilleq la(G)leq lceilrac{Delta(G)+1}{2} ceil$对每个图$G$都成立。本文证明了最大度$Deltageq 33$的1-平面图的线性荫度恰好为$lceilDelta/2 ceil$
关键词: 1-平面图,1-嵌入图,线性荫度
论文图表:
引用
No.****
同行评议
共计0人参与
勘误表
1-平面图的线性荫度
评论
全部评论0/1000