In this paper we consider a problem of job scheduling on parallel machines with a presence of incompatibilities between jobs. The incompatibility relation can be modeled as a complete multipartite graph in which each edge denotes a pair of jobs that cannot be scheduled on the same machine. Our research stems from the works of Bodlaender, Jansen, and Woeginger (1994) and Bodlaender and Jansen (1993). In particular, we pursue the...

In the paper, we show that the incidence chromatic number of a complete k-partite graph is at most ∆+2 (i.e., proving the incidence coloring conjecture for these graphs) and it is equal to ∆+1 if and only if the smallest part has only one vertex.

In this paper, the problem of scheduling on parallel machines with a presence of incompatibilities between jobs is considered. The incompatibility relation can be modeled as a complete multipartite graph in which each edge denotes a pair of jobs that cannot be scheduled on the same machine. The paper provides several results concerning schedules, optimal or approximate with respect to the two most popular criteria of optimality:...

A lot of research has been done on multipartite correlations. However, it seems strange thatthere is no denition of so called genuine multipartite correlations. In this paper we propose threereasonable postulates which each measure or indicator of genuine multipartite correlations (or gen-uine multipartite entanglement) should satisfy. We also introduce degree of correlations which givespartial characterization of multipartite...

We prove that the correlations present in a multipartite quantum state have an operational quantum character even if the state is unentangled, as long as it does not simply encode a multipartite classical probability distribution. Said quantumness is revealed by the new task of local broadcasting, i.e., of locally sharing preestablished correlations, which is feasible if and only if correlations are stricly classical. Our operational...