Preface
Chapter 1 Introduction
1.1 Algorithmic aspects of some vertex partitioning problems
1.1.1 Monochromatic clique and rainbow cycle partitions
1.1.2 Injective coloring problems
1.1.3 Max hypergraph cut with limited unbalance
1.2 Structural aspects of some edge partitioning and related problems
1.2.1 Minimum size of n—factor—critical and k—extendable graphs
1.2.2 Matching alternating Hamilton cycles and directed Hamilton cycles
1.2.3 Structures for augmentation of vertex—disjoint triangle sets
Chapter 2 Minimum monochromatic clique partition and rainbow cycle partition
2.1 Inapproximability of MCLP on monochromatic—K4——free graphs
2.2 An approximation algorithm for WMCLP
2.3 RCYP is NP—complete for triangle—free graphs
2.4 Concluding remarks
Chapter 3 On the complexity of irjective coloring
3.1 Off—line injective coloring
3.1.1 NP—hardness of injective coloring bipartite graphs
3.1.2 On the inapproximability of injective coloring bipartite graphs
3.1.3 An approximation algorithm for the max—injective coloring problem
3.2 On—line injective coloring
3.2.1 P3—free graphs
3.2.2 Triangle—free graphs and bipartite graphs
3.2.3 Concluding remarks
Chapter 4 An approximation algorithm for max hypergraph cut with limited unbalance
4.1 An SDP relaxation of MHC—LU
4.2 Bound on the expected contribution of an edge by Steps 1—4
4.3 Bounding E（ω（Vi， VV1）） after Step 5
4.4 Bounding E（|V1|（m—|V1|））
4.5 The quality of the SDP approximation algorithm
Chapter 5 Minimum size of n—factor—critical and k—extendable grapns
5.1 Minimum size of n—factor—critical graphs and k—extendable bipartite grapns
5.2 Minimum size of 1—extendable non—bipartite graphs and 2—extendable non—bipartite graphs
5.3 Concluding remarks
Chapter 6 Directed Hamilton cycles and matching alternating Hamilton cycles
6.1 Main results
6.2 Proof of Theorem 6.1.2
6.3 Concluding remarks
Chapter 7 Triangle strings： structures for augmentation of vertex—disjoint triangle sets
7.1 Triangle strings
7.2 Union graph of two triangle sets and an augmenting theorem
7.3 Triangle sets in triangle strings： an algorithm and a condition for triangle factors
References
Index
