图的划分:一些进展与未解决问题(英文)  

Graph Partitions:Recent Progresses and Some Open Problems

作　　者：许宝刚[1] 

机构地区：[1]南京师范大学数学科学学院数学研究所,南京江苏210023

出　　处：《数学进展》2016年第1期1-20,共20页Advances in Mathematics（China）

基　　金：Partially supported by NSFC(No.11331003,No.11171160);the Priority Academic Program Development of Jiangsu Higher Education Institutions

摘　　要：图的划分问题是图论研究中最重要的一个问题之一,图论研究的很多问题都是特殊形式的划分问题,比如经典染色理论要求将图划分成最少的独立集,而最大尼-部子图问题则是要找图中边数最多的一个k-部子图.本文给出划分问题的一些最新进展,以及一些尚未解决的问题,其中大部分是来自于求最大k-部子图的相关领域.Graph partition problem is one of the most important topics in structural graph theory, since many problems in graph theory can be treated as a partition of the vertices into sets with some properties. For instance, the classical vertex coloring problem asks for a partition into minimum number of independent sets, and the maximum k-partite subgraph problem asks for a k-partite subgraph with maximum number of edges. In this paper, we present some results and problems on graph partitions, of which most are from the topic originated from the maximum k-partite subgraph problem.

关 键 词：图 划分 进展 问题 

分 类 号：O157.5[理学—数学]