\magnification=1440
\font\bigtenrm=cmr10 scaled\magstep4
Abstract for Aviezri Fraenkel, Even Kernels.

Given a graph $G = (V,E)$, an even kernel is a nonempty
independent subset $V' \subseteq V$, such that every vertex
of $G$ is adjacent to an even number (possibly 0) of 
vertices in $V'$.  It is proved that the question of whether
a graph has an even kernel is NP-complete.  The motivation 
stems from combinatorial game theory.  It is known that this
question is polynomial if $G$ is bipartite.  We also prove that 
the question of whether there is an even kernel whose size is 
between two given bounds, in a given bipartite graph, is NP-complete.
This result has applications in coding and set theory.
\bye