A corrected version of the Duchet kernel conjecture (Q1377724): Difference between revisions

An orientation of edges of a graph is said to be normal if every clique has a kernel. A graph \(G\) is called kernel-solvable if every normal orientation of \(G\) has a kernel. The following theorem is proved: The odd cycles \(C_{2n+1}\), \(n\geq 2\), are the only connected graphs which are not kernel-solvable but removing of any edge produces a kernel-solvable graph.