Characterization of interval graphs that are unpaired 2-disjoint path coverable

Abstract Given disjoint source and sink sets, S = { s 1 , … , s k } and T = { t 1 , … , t k } , in a graph G, an unpaired k-disjoint path cover joining S and T is a set of pairwise vertex-disjoint paths { P 1 , … , P k } that altogether cover every vertex of the graph, in which P i is a path from source s i to some sink t j . In terms of a generalized scattering number, named an r-scattering number, we characterize interval graphs that have an unpaired 2-disjoint path cover joining S and T for any possible configurations of source and sink sets S and T of size 2 each. Also, it is shown that the r-scattering number of an interval graph can be computed in polynomial time.