WQO dichotomy for 3-graphs.

We investigate data-enriched models, like Petri nets with data, whereexecutability of a transition is conditioned by a relation between data valuesinvolved. Decidability status of various decision problems in such models maydepend on the structure of data domain. According to the WQO DichotomyConjecture, if a data domain is homogeneous then it either exhibits a wellquasi-order (in which case decidability follows by standard arguments), oressentially all the decision problems are undecidable for Petri nets over thatdata domain. We confirm the conjecture for data domains being 3-graphs (graphswith 2-colored edges). On the technical level, this results is a significantstep beyond known classification results for homogeneous structures.