Variations of split-coloring in permutation graphs

Combinatorial optimization problems related to permutations have been widely studied. Here, we consider different generalizations of the usual coloring problem in permutation graphs. A cocoloring is a partition of a permutation into increasing and decreasing subsequences. A split-coloring of permutation graphs corresponds to a partition of a given permutation into a minimum number of combinations of an increasing and a decreasing subsequences. We give two applications of Min Split-coloring in permutation graphs. The second one gives rise to a new problem, called Min Ordered Collecting, in permutations. Although this problem turns out to be NP-hard, we give polynomial time algorithms for some cases. We also introduce the Min Threshold-coloring which is closely related to, but different from, Min Ordered Collecting in permutations. We show that Min Cocoloring reduces to Min Threshold-coloring under some conditions. We prove that Min Split-coloring, Min Threshold-coloring and Min Cocoloring are all NP-hard in triangle-free graphs.