短圈不相交的平面图的线性2-荫度
发布时间：2018-11-08 10:52
【摘要】：图的染色理论是图论的研究热点,研究了平面图的线性2-荫度问题,该问题在平面图的染色及分解方面有重要的意义.设图G(V,E)是简单平面图,△(G)表示图G的最大度.图G的线性2-荫度la2(G)是将图G分解为k个边不交的线性2-森林的最小整数k,其中线性2-森林是指每个分支树均为长度至多为2的路的图.如果两个圈至少有一个公共点,则称两圈相交.如果两个圈至少有一条公共边,则称两圈相邻.得到了若干不含相交短圈的平面图的线性2-荫度的上界,主要结论有：(1)若图G为不含相交3-圈或者不含相交4-圈的平面图,则(21若图G为不含相交3-圈且不含相交4-圈的平面图,则(3)若图G为任一3-圈与5-圈不相交的平面图,则给出了不含相邻短圈的平面图的线性2-荫度的一个上界.设图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
[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
本文链接：https://www.wllwen.com/kejilunwen/yysx/2318244.html
