8 citations · 9 across the 3 of their papers we have counts for
3 papers
math.CO2008★ 1 cited
Splitting finite antichains in the homomorphism order
Jan Foniok, Jaroslav Nesetril
A structural condition is given for finite maximal antichains in the homomorphism order of relational structures to have the splitting property. It turns out that non-splitting ant…
math.CO2007★ 8 cited
Homomorphisms and Structural Properties of Relational Systems
Jan Foniok
Two main topics are considered: The characterisation of finite homomorphism dualities for relational structures, and the splitting property of maximal antichains in the homomorphis…
cs.CC2007
P-matrix recognition is co-NP-complete
Jan Foniok
This is a summary of the proof by G.E. Coxson that P-matrix recognition is co-NP-complete. The result follows by a reduction from the MAX CUT problem using results of S. Poljak and…