【摘要】：圖的染色理論是圖論的研究熱點(diǎn),研究了平面圖的線性2-蔭度問題,該問題在平面圖的染色及分解方面有重要的意義.設(shè)圖G(V,E)是簡單平面圖,△(G)表示圖G的最大度.圖G的線性2-蔭度la2(G)是將圖G分解為k個邊不交的線性2-森林的最小整數(shù)k,其中線性2-森林是指每個分支樹均為長度至多為2的路的圖.如果兩個圈至少有一個公共點(diǎn),則稱兩圈相交.如果兩個圈至少有一條公共邊,則稱兩圈相鄰.得到了若干不含相交短圈的平面圖的線性2-蔭度的上界,主要結(jié)論有：(1)若圖G為不含相交3-圈或者不含相交4-圈的平面圖,則(21若圖G為不含相交3-圈且不含相交4-圈的平面圖,則(3)若圖G為任一3-圈與5-圈不相交的平面圖,則給出了不含相鄰短圈的平面圖的線性2-蔭度的一個上界.設(shè)圖G是平面圖,若任一i-圈與j-圈不相鄰,其中i,j∈{3,4},則有
[Abstract]:The coloring theory of graphs is a hot topic in graph theory. The problem of linear 2-shade degree of planar graphs is studied. This problem is of great significance in the coloring and decomposition of planar graphs. Let G be a simple planar graph, and (G) denote the maximum degree of G. The linear 2-ring degree la2 (G) of a graph G is the smallest integer kof a graph G decomposing into k edge disjoint linear 2-forests, where a linear 2-forest is a graph in which each branch tree is a path of up to 2 in length. If two circles have at least one common point, the two circles intersect. If two circles have at least one common edge, they are said to be adjacent. In this paper, we obtain the upper bounds of the linear 2-arboricity of some planar graphs without intersecting short cycles. The main results are as follows: (1) if G is a planar graph with no intersecting 3-cycles or no intersecting 4-cycles, Then (21) if G is a planar graph with no intersecting 3-cycle and no intersecting 4-cycle, then (3) if G is a planar graph with any 3-cycle and 5-cycle disjoint, Then an upper bound of the linear 2-shade degree of a planar graph without adjacent short cycles is given. Let G be a planar graph, if any i- cycle is not adjacent to the j-cycle, where iGJ 鈭，

本文編號：2318244