Graph Partitions:Recent Progresses and Some Open Problems
Baogang Xu · 2016
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.