目录 PrefaceChapter 1Introduction1.1Algorithmic aspects of some vertex partitioning problems1.1.1Monochromatic clique and rainbow cycle partitions1.1.2Injective coloring problems1.1.3Max hypergraph cut with limited unbalance1.2Structural aspects of some edge partitioning and related problems1.2.1Minim size of n-factor-critical and k-extendable graphs1.2.2Matching alternating Hamilton cycles and directed Hamilton cycles1.2.3Structures for augmentation of vertex-disjoint triangle setsChapter 2Minim monochromatic clique partition and rainbow cycle partition2.1Inappromability of MCLP on monochromatic-K4-free graphs2.2An appromation algorithm for WMCLP2.3RCYP is NP-complete for triangle-free graphs2.4Concluding remarksChapter 3On the complety of injective coloring3.1Off-line injective coloring3.1.1NP-hardness of injective coloring bipartite graphs3.1.2On the inappromability of injective coloring bipartite graphs3.1.3An appromation algorithm for the max-injective coloring problem3.2On-line injective coloring3.2.1P3-free graphs3.2.2Triangle-free graphs and bipartite graphs3.2.3Concluding remarksChapter 4An appromation algorithm for max hypergraph cut with limited unbalance4.1An SDP relaxation of MHC-LU4.2Bound on the expected contribution of an edge by Steps 1-44.3Bounding E[w(V1, Y \ V1)] after Step 54.4Bounding E[V1(m-V1)]4.5The quality of the SDP appromation algorithmChapter 5Minim size of n-factor-critical and k-extendable graphs5.1Minim size of n-factor-critical graphs and k-extendable bipartite graphs5