The p-partitioning and p-coloring problems on a Bethe lattice of coordination number z are analyzed. It is shown that these two NP-complete optimization problems turn out to be equivalent to finding the ground-state energy of p-state Potts models with frustration. Numerical calculation of the cost function of both problems are carried out for several values of z and p. In the case of p = 2 the results are identical to those obtained by Mezard and Parisi for the case of the bipartitioning problem. A numerical upper bound to the chromatic number is found for several values of z.