  We generalize the theory of k-core percolation on complex networks to k-core
percolation on multiplex networks, where k=(k_a, k_b, ...). Multiplex networks
can be defined as networks with a set of vertices but different types of edges,
a, b, ..., representing different types of interactions. For such networks, the
k-core is defined as the largest sub-graph in which each vertex has at least
k_i edges of each type, i = a, b, ... . We derive self-consistency equations to
obtain the birth points of the k-cores and their relative sizes for
uncorrelated multiplex networks with an arbitrary degree distribution. To
clarify our general results, we consider in detail multiplex networks with
edges of two types, a and b, and solve the equations in the particular case of
ER and scale-free multiplex networks. We find hybrid phase transitions at the
emergence points of k-cores except the (1,1)-core for which the transition is
continuous. We apply the k-core decomposition algorithm to air-transportation
multiplex networks, composed of two layers, and obtain the size of (k_a,
k_b)-cores.
