Hits :

First Author : 钱景

Affiliation of Author(s): 数理与信息工程学院

Date of Publication : 2008-01-01

Document Type : 期刊

Journal : 运筹学学报

Issue : 第4期

Page Number : 48

ISSN : 1007-6093

Translation or Not : no

Key Words : 运筹学；图论；K_4-minor-free图；树；线性2-荫度

Abstract : 图G的线性2-荫度la_2(G)是将G分解为k个边不交的森林的最小整数k,其中每个森林的分支树是长度至多为2的路.本文证明了若G是最大度为Δ(G)的K_4-minor-free图,则la_2(G)≤(Δ(G)+5)/2.