k-core percolation is an extension of the concept of classical percolation and is particularly relevant to understanding the resilience of complex networks under random damage. A new analytical formalism has been recently proposed to deal with heterogeneous k-cores, where each vertex is assigned a local threshold k(i). In this Letter we identify a binary mixture of heterogeneous k-cores which exhibits a tricritical point. We investigate the new scaling scenario and calculate the relevant critical exponents, by analytical and computational methods, for Erdos-Renyi networks and 2D square lattices.