Even kernels (Q1346724)

Summary: 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.