IC-平面图的线性荫度

Linear Arboricity of IC-Planar Graphs

图G的边分解是指将G分解成子图G1,G2,...,Gm,使得E(G)=E(G_(1))∪…∪E(G_(m)),且对任意i≠j,有E(G_(i))∩E(G_(j))=φ.若一个森林的每个连通分支都是路,则称该森林为线性森林.图G的线性荫度la(G)是指使得G可以边分解为m个线性森林的最小整数m.本文证明了Δ(G)≥15的IC-平面图G的线性荫度为[Δ(G)/2],这里Δ(G)是图G的最大度.

An edge-part it ion of a graph G is a decomposition of G into subgraphs G1,G2,…,Gmsuch that E(G)=E(G1) ∪…∪ E(Gm) and E(Gi)∩E(Gj)=φ for i≠j.A linear forest is a forest in which each connected component is a path.The linear arboricity la(G) is the least integer m such that G can be edge-partitioned into m linear forests.In this paper,we study the linear arboricity la(G) of IC-planar graphs,and prove that la(G)=[Δ(G)/2] for each IC-planar graph G with Δ(G)≥15,whereΔ(G) is the maximum degree of G.