Some advanced topics of graph partitioning and matching problems9787030495020

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