In English, we usually only put a possessive on the second person possessing - "Fratisek is Matej and Zofie's father" should be accepted (and afaik is actually the more correct version).

I have to concur. I'm an English teacher and, without specific context, it is unnatural to have the double possessive in English.

I understand that both of these are čeho declined in Czech but they wouldn't be naturally possessive in English.