Contents Preface Chapter 1 Introduction 1 1.1 Algorithmic aspects of some vertex partitioning problems 4 1.1.1 Monochromatic clique and rainbow cycle partitions 4 1.1.2 Injective coloring problems 7 1.1.3 Max hypergraph cut with limited unbalance 9 1.2 Structural aspects of some edge partitioning and related problems 15 1.2.1 Minimum size of n-factor-critical and k-extendable graphs 15 1.2.2 Matching alternating Hamilton cycles and directed Hamilton cycles 16 1.2.3 Structures for augmentation of vertex-disjoint triangle sets 19 Chapter 2 Minimum monochromatic clique partition and rainbow cycle partition 22 2.1 Inapproximability of MCLP on monochromatic-*free graphs 22 2.2 An approximation algorithm for WMCLP 26 2.3 RCYP is NP-complete for triangle-free graphs 30 2.4 Concluding remarks 33 Chapter 3 On the complexity of injective coloring 35 3.1 Off-line injective coloring 35 3.1.1 NP-hardness of injective coloring bipartite graphs 35 3.1.2 On the inapproximability of injective coloring bipartite graphs 37 3.1.3 An approximation algorithm for the max-injective coloring problem 39 3.2 On-line injective coloring 42 3.2.1 P3-free graphs 44 3.2.2 Triangle-free graphs and bipartite graphs 44 3.2.3 Concluding remarks 49 Chapter 4 An approximation algorithm for max hypergraph cut with limited unbalance 50 4.1 An SDP relaxation of MHC-LU 50 4.2 Bound on the expected contribution of an edge by Steps 1-4 56 4.3 Bounding * after Step 5 69 4.4 Bounding * 71 4.5 The quality of the SDP approximation algorithm 75 Chapter 5 Minimum size of n-factor-critical and k-extendable graphs 85 5.1 Minimum size of n-factor-critical graphs and k-extendable bipartite graphs 86 5.2 Minimum size of 1-extendable non-bipartite graphs and 2-extendable non-bipartite graphs 90 5.3 Concluding remarks 101 Chapter 6 Directed Hamilton cycles and matching alternating Hamilton cycles 102 6.1 Main results 102 6.2 Proof of Theorem 6.1.2 106 6.3 Concluding remarks 122 Chapter 7 Triangle strings: structures for augmentation of vertex-disjoint triangle sets 124 7.1 Triangle strings 125 7.2 Union graph of two triangle sets and an augmenting theorem 126 7.3 Triangle sets in triangle strings: an algorithm and a condition for triangle factors 133 References 138 Index 149