An Automatic Test Pattern Generation (ATPG) tool is presented that generates compact test sets that test concurrently the digital embedded cores in a System on Chip. The approach is driven by novel graph theoretic problem formulation to generate patterns for two or more cores in parallel. Pairs of input lines from different cores as well as pairs of output lines are systematically allocated on the same Test Access Mechanism (TAM) lines to improve the efficiency of the ATPG. The approach enables core integrators to determine which pairs of cores can be tested concurrently with the same test bus. Low application time for 100% single stuck-at fault coverage is sought subject to a given TAM bandwidth. The experimental results show drastic reductions in the test application time over the conventional ATPG method that generates tests for each core separately.