图的染色和控制集问题的理论和算法研究

项目名称： 图的染色和控制集问题的理论和算法研究

项目编号： No.10971248

项目类型： 面上项目

立项/批准年度： 2010

项目学科： 数理科学和化学

项目作者： 吕长虹

作者单位： 华东师范大学

项目金额： 25万元

中文摘要： 图染色一直是图论研究的主流问题，在理论和应用方面均有其积极意义。图的控制集问题及其各种推广形式是目前图论研究发展最快的领域之一。图的染色和控制集问题均与图的结构具有密切联系,其研究主要涉及到组合图论方法,随机方法,代数方法,线性规划以及由此产生的各种算法。本项目主要考虑各种形式的染色问题和控制集问题的性质和算法。主要内容有：一，围绕 M.Karonski等人在 2004年提出的猜想,对一般图或特殊图类vertex-coloring edge-weightings及相关问题的参数进行估计,包括极图的刻画等；二，采用组合手段,代数和随机方法,结合新的first-fit思想，对L(j,k)-labling等问题提供一些新的技术和想法；三，考虑chordal graphs及其子图类上各种控制集问题的有效算法。

中文关键词： L(2;1)-标号；路覆盖数；控制集；算法；

英文摘要：

英文关键词： L(2;1)-labeling；path covering number；domination；algorithm；