Bounding signed series-parallel graphs and cores of signed $K_4$-subdivisions

Abstract

We study homomorphism properties of signed $K_4$-minor-free graphs. On the one hand, we give a necessary and sufficient condition for a signed graph $B$ to admit a homomorphism from any signed $K_4$-minor-free graph and we determine the smallest of all such signed graphs. On the other hand, we characterize the minimal cores that do not belong to the class of signed $K_4$-minor-free graphs. This, in particular, gives a classification of odd-$K_4$’s that are cores. Furthermore, we show some applications of our work.